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

DOI10.1137/21M1422781arXiv2010.04985OpenAlexW4389392633MaRDI QIDQ6139835FDOQ6139835

Tom Gur, Oded Lachish, Author name not available (Why is that?)

Publication date: 19 December 2023

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

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.

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)

Cites Work

• Title not available (Why is that?)
• Proof verification and the hardness of approximation problems
• Property testing and its connection to learning and approximation
• Locally testable codes and PCPs of almost-linear length
• Probabilistic checking of proofs
• Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
• Sound 3-Query PCPPs Are Long
• Robust Characterizations of Polynomials with Applications to Program Testing
• Three theorems regarding testing graph properties
• Private vs. common random bits in communication complexity
• A unified framework for testing linear‐invariant properties
• Towards 3-query locally decodable codes of subexponential length
• Short Locally Testable Codes and Proofs
• On the efficiency of local decoding procedures for error-correcting codes
• Locally decodable codes
• Two-query PCP with subconstant error
• Error-correcting data structures
• On the randomness complexity of property testing
• Introduction to Property Testing
• The power and limitations of uniform samples in testing properties of figures
• Title not available (Why is that?)
• An adaptivity hierarchy theorem for property testing
• Arguments of Proximity
• A Hierarchy Theorem for Interactive Proofs of Proximity
• Partial tests, universal tests and decomposability
• Interactive proofs of proximity
• 3-Query Locally Decodable Codes of Subexponential Length
• Non-interactive proofs of proximity
• Composition of Low-Error 2-Query PCPs Using Decodable PCPs
• Constant-Round Interactive Proofs for Delegating Computation
• Zero-Knowledge Proofs of Proximity
• On Sample-Based Testers
• On the Power of Relaxed Local Decoding Algorithms
• Testing convexity of figures under the uniform distribution
• Sample-Based High-Dimensional Convexity Testing.
• Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity
• Every Set in P Is Strongly Testable Under a Suitable Encoding

Cited In (4)

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

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)