English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We study local filters for the Lipschitz property of real-valued functions$f: V \to [0,r]$, where the Lipschitz property is defined with respect to anarbitrary undirected graph $G=(V,E)$. We give nearly optimal local Lipschitzfilters both with respect to $\ell_1$-distance and $\ell_0$-distance. Previouswork only considered unbounded-range functions over $[n]^d$. Jha andRaskhodnikova (SICOMP `13) gave an algorithm for such functions with lookupcomplexity exponential in $d$, which Awasthi et al. (ACM Trans. Comput. Theory)showed was necessary in this setting. We demonstrate that importantapplications of local Lipschitz filters can be accomplished with filters forfunctions with bounded-range. For functions $f: [n]^d\to [0,r]$, we circumventthe lower bound and achieve running time $(d^r\log n)^{O(\log r)}$ for the$\ell_1$-respecting filter and $d^{O(r)}\text{polylog } n$ for the$\ell_0$-respecting filter. Our local filters provide a novel Lipschitzextension that can be implemented locally. Furthermore, we show that ouralgorithms have nearly optimal dependence on $r$ for the domain $\{0,1\}^d$. Inaddition, our lower bound resolves an open question of Awasthi et al., removingone of the conditions necessary for their lower bound for general range. Weprove our lower bound via a reduction from distribution-free Lipschitz testingand a new technique for proving hardness for {\em adaptive} algorithms. Weprovide two applications of our local filters to arbitrary real-valuedfunctions. In the first application, we use them in conjunction with theLaplace mechanism for differential privacy and noisy binary search to providemechanisms for privately releasing outputs of black-box functions, even in thepresence of malicious clients. In the second application, we use our localfilters to obtain the first nontrivial tolerant tester for the Lipschitzproperty.

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