Universal locally verifiable codes and 3-round interactive proofs of proximity for CSP

DOI10.1016/j.tcs.2021.05.030OpenAlexW3168770271WikidataQ113863196 ScholiaQ113863196MaRDI QIDQ2043015

Tom Gur, Oded Goldreich

Publication date: 22 July 2021

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2021.05.030

zbMATH Keywords

coding theoryproperty testinglocally testable codesprobabilistic proof systems

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (2)

A Hierarchy Theorem for Interactive Proofs of Proximity ⋮ An exponential separation between \textsf{MA} and \textsf{AM} proofs of proximity

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fast approximate probabilistically checkable proofs
• Time-Optimal Interactive Proofs for Circuit Evaluation
• Non-Interactive Proofs of Proximity
• Proofs of Proximity for Context-Free Languages and Read-Once Branching Programs
• Locally testable codes and PCPs of almost-linear length
• Some 3CNF properties are hard to test
• Simple PCPs with poly-log rate and query complexity
• The Probabilistic Communication Complexity of Set Intersection
• Algebraic methods for interactive proof systems
• Interactive proofs and the hardness of approximating cliques
• A Hierarchy Theorem for Interactive Proofs of Proximity
• Robust Characterizations of Polynomials with Applications to Program Testing
• Property Testing of Massively Parametrized Problems – A Survey
• Proofs of Proximity for Distribution Testing
• An Exponential Separation Between MA and AM Proofs of Proximity
• Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity
• Distribution Testing Lower Bounds via Reductions from Communication Complexity
• Constant-round interactive proofs for delegating computation
• Interactive proofs of proximity
• Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
• Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem
• Computational Complexity
• The PCP theorem by gap amplification

This page was built for publication: Universal locally verifiable codes and 3-round interactive proofs of proximity for CSP