From local to robust testing via agreement testing

DOI10.4086/TOC.2022.V018A012MaRDI QIDQ5093398zbMATH OpenOpenAlexFDO

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

Publication date 26 July 2022

Published in Theory of Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4086/toc.2022.v018a012

zbMATH Keywords

affine-invariant codeslifted codeslocal testingagreement testingrobust soundness

Mathematics Subject Classification ID

Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Theory of computing (68Qxx)

Recommendations

• From Local to Robust Testing via Agreement Testing
• Robust locally testable codes and products of codes
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Absolutely sound testing of lifted codes
• Absolutely sound testing of lifted codes

Cites work

• scientific article; zbMATH DE number 1559563 (Why is no real title available?)
• A Combinatorial Consistency Lemma with Application to Proving the PCP Theorem
• A combination of testability and decodability by tensor products
• Absolutely sound testing of lifted codes
• Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem
• Composition of semi-LTCs by two-wise tensor products
• Exponentially small soundness for the direct product Z-test
• From Local to Robust Testing via Agreement Testing
• Improved low-degree testing and its applications
• Interactive proofs and the hardness of approximating cliques
• New affine-invariant codes from lifting
• New direct-product testers and 2-query PCPs
• Non-deterministic exponential time has two-prover interactive protocols
• Probabilistic checking of proofs
• Proof verification and the hardness of approximation problems
• Robust Characterizations of Polynomials with Applications to Program Testing
• Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
• Robust locally testable codes and products of codes
• Self-testing/correcting with applications to numerical problems
• Some 3CNF Properties Are Hard to Test
• Uniform direct product theorems: simplified, optimized, and derandomized

Cited in

(2)

• Testing equality under the local broadcast model
• From Local to Robust Testing via Agreement Testing

This page was built for publication: From local to robust testing via agreement testing

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