Lune

SODA2025Top-tier venue

Local Lipschitz Filters for Bounded-Range Functions with Applications to Arbitrary Real-Valued Functions

Jane Lange, Ephraim Linder, Sofya Raskhodnikova, Arsen Vasilyan

Abstract

We study local filters for the Lipschitz property of real-valued functions f : V → [0, r], where the Lipschitz property is defined with respect to an arbitrary undirected graph G = (V, E). We give nearly optimal local Lipschitz filters both with respect to ℓ1-distance and ℓ0-distance. Previous work only considered unbounded-range functions over [n] d . Jha and Raskhodnikova (SICOMP '13) gave an algorithm for such functions with lookup complexity exponential in d, which Awasthi et al. (ACM Trans. Comput. Theory) showed was necessary in this setting. We demonstrate that important applications of local Lipschitz filters can be accomplished with filters for functions whose range is bounded in [0, r]. For functions f : [n] d → [0, r], we achieve running time (d r log n) O(log r) for the ℓ1-respecting filter and d O(r) polylog n for the ℓ0-respecting filter, thus circumventing the lower bound. Our local filters provide a novel Lipschitz extension that can be implemented locally. Furthermore, we show that our algorithms are nearly optimal in terms of the dependence on r for the domain 0, 1 d , an important special case of the domain [n] d . In addition, our lower bound resolves an open question of Awasthi et al., removing one of the conditions necessary for their lower bound for general range. We prove our lower bound via a reduction from distribution-free Lipschitz testing and a new technique for proving hardness for adaptive algorithms.

Finally, we provide two applications of our local filters to real-valued functions, with no restrictions on the range. In the first application, we use them in conjunction with the Laplace mechanism for differential privacy and noisy binary search to provide mechanisms for privately releasing outputs of black-box functions, even in the presence of malicious clients. In particular, our differentially private mechanism for arbitrary real-valued functions runs in time 2 polylog min (r,nd) and, for honest clients, has accuracy comparable to the Laplace mechanism for Lipschitz functions, up to a factor of O(log min(r, nd)). In the second application, we use our local filters to obtain the first nontrivial tolerant tester for the Lipschitz property. Our tester works for functions of the form f : 0, 1 d → R, makes 2 O( √ d) queries, and has tolerance ratio 2.01. Our applications demonstrate that local filters for bounded-range functions can be applied to construct efficient algorithms for arbitrary real-valued functions.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

2 top-tier papers have cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Properly learning monotone functions via local correction cites Approximating the Distance to Monotonicity of Boolean Functions
  • Properly learning monotone functions via local correction cites Local Computation of Maximal Independent Set
  • Improved Local Computation Algorithms for Greedy Set Cover via Retroactive Updates cites Properly learning monotone functions via local correction
  • Improved Local Computation Algorithms for Greedy Set Cover via Retroactive Updates cites Local Computation of Maximal Independent Set
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers2

  1. Privately Evaluating Untrusted Black-Box FunctionsEphraim Linder, Sofya Raskhodnikova, Adam Smith, Thomas SteinkeSTOC 2025 · 1 citation
  2. Improved Local Computation Algorithms for Greedy Set Cover via Retroactive UpdatesSlobodan Mitrovic, Srikkanth Ramachandran, Ronitt Rubinfeld, Mihir SinghalSTOC 2026

Builds on6

  1. Covariance-Aware Private Mean Estimation Without Private Covariance EstimationGavin Brown, Marco Gaboardi, Adam D. Smith, Jonathan R. Ullman et al.NeurIPS 2021 · 59 citations
  2. Widespread Underestimation of Sensitivity in Differentially Private Libraries and How to Fix ItSílvia Casacuberta, Michael Shoemate, Salil P. Vadhan, Connor WagamanCCS 2022 · 12 citations
  3. Local Computation of Maximal Independent SetMohsen GhaffariFOCS 2022 · 8 citations
  4. Approximating the Distance to Monotonicity of Boolean FunctionsRamesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Erik WaingartenSODA 2020 · 6 citations
  5. Properly learning monotone functions via local correctionJane Lange, Ronitt Rubinfeld, Arsen VasilyanFOCS 2022 · 5 citations

Related papers

  1. Private Identity Testing for High-Dimensional DistributionsClément L. Canonne, Gautam Kamath, Audra McMillan, Jonathan R. Ullman et al.NeurIPS 2020 · 42 citations
  2. Smooth Sensitivity for Geo-PrivacyYuting Liang, Ke YiCCS 2024 · 1 citation
  3. Instance-optimality in differential privacy via approximate inverse sensitivity mechanismsHilal Asi, John C. DuchiNeurIPS 2020 · 72 citations
  4. Confidence Intervals for Private Query ProcessingDajun Sun, Wei Dong, Ke YiVLDB 2024 · 5 citations
  5. Local Dampening: Differential Privacy for Non-numeric Queries via Local SensitivityVictor A. E. de Farias, Felipe T. Brito, Cheryl J. Flynn, Javam C. Machado et al.VLDB 2021 · 20 citations
Dusk over the sea between two cliffs drawn in fine vertical lines