Every Set in P Is Strongly Testable Under a Suitable Encoding

DOI10.4230/LIPICS.ITCS.2019.30OpenAlexW2912558601MaRDI QIDQ5090404FDOQ5090404

Authors: Irit Dinur, Oded Goldreich, Tom Gur 

Publication date: 18 July 2022

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

Recommendations

• Probabilistically checkable proofs and codes
• Smooth and strong PCPs
• Strong locally testable codes with relaxed local decoders
• Locally testable codes and PCPs of almost-linear length
• Near-Testable Sets

zbMATH Keywords

property testingprobabilistically checkable proofs

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• 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
• Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
• Efficient testing of large graphs
• Property testing in bounded degree graphs
• Self-testing/correcting with applications to numerical problems
• Computational Complexity
• A combinatorial characterization of the testable graph properties, it's all about regularity
• Hierarchy theorems for property testing
• The PCP theorem by gap amplification
• Introduction to Property Testing
• Strong locally testable codes with relaxed local decoders
• On Proximity-Oblivious Testing
• Non-interactive proofs of proximity
• Relaxed locally correctable codes
• Two-sided error proximity oblivious testing

Cited In (2)

• A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Verification
• Robustly self-ordered graphs: constructions and applications to property testing

This page was built for publication: Every Set in P Is Strongly Testable Under a Suitable Encoding

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