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

DOI10.1137/21m1422781arXiv2010.04985OpenAlexW4389392633MaRDI QIDQ6139835

Tom Gur, Oded Lachish, Unnamed Author

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

adaptivitycoding theoryproperty testinglocal algorithmssample-based algorithmssunflower lemmas

Mathematics Subject Classification ID

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

Cites Work

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

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