Every Set in P Is Strongly Testable Under a Suitable Encoding

DOI10.4230/LIPICS.ITCS.2019.30MaRDI QIDQ5090404zbMATH OpenOpenAlexFDO

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/

zbMATH Keywords

property testingprobabilistically checkable proofs

Mathematics Subject Classification ID

Theory of computing (68Qxx)

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

Cites work

• A combinatorial characterization of the testable graph properties, it's all about regularity
• Computational Complexity
• Efficient testing of large graphs
• Hierarchy theorems for property testing
• Introduction to Property Testing
• Locally testable codes and PCPs of almost-linear length
• Non-interactive proofs of proximity
• On Proximity-Oblivious Testing
• Probabilistic checking of proofs
• Proof verification and the hardness of approximation problems
• Property testing and its connection to learning and approximation
• Property testing in bounded degree graphs
• Relaxed locally correctable codes
• Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
• Self-testing/correcting with applications to numerical problems
• Short PCPs with Polylog Query Complexity
• Strong locally testable codes with relaxed local decoders
• The PCP theorem by gap amplification
• Two-sided error proximity oblivious testing

Cited in

(2)

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

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)