Every Set in P Is Strongly Testable Under a Suitable Encoding

DOI10.4230/LIPIcs.ITCS.2019.30OpenAlexW2912558601MaRDI QIDQ5090404

Tom Gur, Oded Goldreich, Irit Dinur

Publication date: 18 July 2022

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2018/10123/pdf/LIPIcs-ITCS-2019-30.pdf/

zbMATH Keywords

probabilistically checkable proofsproperty testing

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items

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

Cites Work

• Unnamed Item
• Unnamed Item
• Hierarchy theorems for property testing
• Self-testing/correcting with applications to numerical problems
• Non-interactive proofs of proximity
• Two-sided error proximity oblivious testing
• A combinatorial characterization of the testable graph properties
• On Proximity-Oblivious Testing
• 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
• Short PCPs with Polylog Query Complexity
• Probabilistic checking of proofs
• Introduction to Property Testing
• Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
• Computational Complexity
• The PCP theorem by gap amplification
• Efficient testing of large graphs
• Property testing in bounded degree graphs