From Local to Robust Testing via Agreement Testing

DOI10.4230/LIPIcs.ITCS.2019.29OpenAlexW2937040716MaRDI QIDQ5090403

Noga Ron-Zewi, Irit Dinur, Tali Kaufman, Prahladh Harsha

Publication date: 18 July 2022

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

zbMATH Keywords

robust testingaffine-invariant codeslifted codeslocal testingagreement testing

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items

Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Composition of semi-LTCs by two-wise tensor products
• Improved low-degree testing and its applications
• New affine-invariant codes from lifting
• On Sums of Locally Testable Affine Invariant Properties
• Proof verification and the hardness of approximation problems
• Probabilistic checking of proofs
• High-Rate Locally Correctable and Locally Testable Codes with Sub-Polynomial Query Complexity
• Robust Characterizations of Polynomials with Applications to Program Testing
• New Direct-Product Testers and 2-Query PCPs
• A Combinatorial Consistency Lemma with Application to Proving the PCP Theorem
• A combination of testability and decodability by tensor products
• Robust locally testable codes and products of codes
• Some 3CNF Properties Are Hard to Test
• Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
• Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem