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 Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

We prove a general structural theorem for a wide family of local algorithms,which includes property testers, local decoders, and PCPs of proximity. Namely,we show that the structure of every algorithm that makes $q$ adaptive queriesand satisfies a natural robustness condition admits a sample-based algorithmwith $n^{1- 1/O(q^2 \log^2 q)}$ sample complexity, following the definition ofGoldreich and Ron (TOCT 2016). We prove that this transformation is nearlyoptimal. Our theorem also admits a scheme for constructing privacy-preservinglocal algorithms. Using the unified view that our structural theorem provides,we obtain results regarding various types of local algorithms, including thefollowing.  - We strengthen the state-of-the-art lower bound for relaxed locallydecodable codes, obtaining an exponential improvement on the dependency inquery complexity; this resolves an open problem raised by Gur and Lachish(SICOMP 2021).  - We show that any (constant-query) testable property admits a sample-basedtester with sublinear sample complexity; this resolves a problem left open in awork of Fischer, Lachish, and Vasudev (FOCS 2015) by extending their mainresult to adaptive testers.  - We prove that the known separation between proofs of proximity and testersis essentially maximal; this resolves a problem left open by Gur and Rothblum(ECCC 2013, Computational Complexity 2018) regarding sublinear-time delegationof computation.  Our techniques strongly rely on relaxed sunflower lemmas and theHajnal-Szemer\'edi theorem.

A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Verification