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

DOI10.1137/21M1422781MaRDI QIDQ6139835zbMATH OpenOpenAlexFDO

Authors Tom Gur, Oded Lachish

Publication date 19 December 2023

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2010.04985

zbMATH Keywords

adaptivityproperty testingcoding theorylocal algorithmssample-based algorithmssunflower lemmas

Mathematics Subject Classification ID

Applications of graph theory (05C90) Analysis of algorithms (68W40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) General topics of discrete mathematics in relation to computer science (68R01)

Abstract: 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 queries and satisfies a natural robustness condition admits a sample-based algorithm with $n^{1-1/O(q^{2}lo{g}^{2}q)}$ sample complexity, following the definition of Goldreich and Ron (TOCT 2016). We prove that this transformation is nearly optimal. Our theorem also admits a scheme for constructing privacy-preserving local algorithms. Using the unified view that our structural theorem provides, we obtain results regarding various types of local algorithms, including the following. - We strengthen the state-of-the-art lower bound for relaxed locally decodable codes, obtaining an exponential improvement on the dependency in query complexity; this resolves an open problem raised by Gur and Lachish (SODA 2020). - We show that any (constant-query) testable property admits a sample-based tester with sublinear sample complexity; this resolves a problem left open in a work of Fischer, Lachish, and Vasudev (FOCS 2015) by extending their main result to adaptive testers. - We prove that the known separation between proofs of proximity and testers is essentially maximal; this resolves a problem left open by Gur and Rothblum (ECCC 2013, Computational Complexity 2018) regarding sublinear-time delegation of computation. Our techniques strongly rely on relaxed sunflower lemmas and the Hajnal-Szemer'edi theorem.

Cites work

• scientific article; zbMATH DE number 3344609 (Why is no real title available?)
• 3-query locally decodable codes of subexponential length
• A hierarchy theorem for interactive proofs of proximity
• A unified framework for testing linear-invariant properties
• An adaptivity hierarchy theorem for property testing
• Arguments of proximity (extended abstract)
• Composition of low-error 2-query PCPs using decodable PCPs
• Constant-round interactive proofs for delegating computation
• Error-correcting data structures
• Every Set in P Is Strongly Testable Under a Suitable Encoding
• Interactive proofs of proximity: delegating computation in sublinear time
• Introduction to Property Testing
• Locally decodable codes
• Locally testable codes and PCPs of almost-linear length
• Non-interactive proofs of proximity
• On sample-based testers
• On the efficiency of local decoding procedures for error-correcting codes
• On the power of relaxed local decoding algorithms
• On the randomness complexity of property testing
• Partial tests, universal tests and decomposability
• Private vs. common random bits in communication complexity
• Probabilistic checking of proofs
• Proof verification and the hardness of approximation problems
• Property testing and its connection to learning and approximation
• Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity
• Robust Characterizations of Polynomials with Applications to Program Testing
• Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
• Sample-based high-dimensional convexity testing
• Short locally testable codes and proofs
• Sound 3-query PCPPs are long
• Testing convexity of figures under the uniform distribution
• The power and limitations of uniform samples in testing properties of figures
• Three theorems regarding testing graph properties
• Towards 3-query locally decodable codes of subexponential length
• Two-query PCP with subconstant error
• Universal locally testable codes
• Zero-knowledge proofs of proximity

Cited in

(4)

• Algebraic method for generation of locally trivial tests
• A probabilistic algorithm to test local algebraic observability in polynomial time
• A new approach on locally checkable problems
• Reducing the time complexity of testing for local threshold testability

This page was built for publication: A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Verification

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6139835)