From local to robust testing via agreement testing
From MaRDI portal
Publication:5093398
DOI10.4086/TOC.2022.V018A012OpenAlexW4285277870MaRDI QIDQ5093398FDOQ5093398
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)
Full work available at URL: https://doi.org/10.4086/toc.2022.v018a012
Recommendations
Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Theory of computing (68Qxx)
Cites Work
- Proof verification and the hardness of approximation problems
- Probabilistic checking of proofs
- Interactive proofs and the hardness of approximating cliques
- Title not available (Why is that?)
- A Combinatorial Consistency Lemma with Application to Proving the PCP Theorem
- Robust locally testable codes and products of codes
- Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
- Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem
- Self-testing/correcting with applications to numerical problems
- Robust Characterizations of Polynomials with Applications to Program Testing
- Some 3CNF Properties Are Hard to Test
- Non-deterministic exponential time has two-prover interactive protocols
- Improved low-degree testing and its applications
- Composition of semi-LTCs by two-wise tensor products
- Uniform direct product theorems: simplified, optimized, and derandomized
- New affine-invariant codes from lifting
- From Local to Robust Testing via Agreement Testing
- New direct-product testers and 2-query PCPs
- A combination of testability and decodability by tensor products
- Absolutely sound testing of lifted codes
- Exponentially small soundness for the direct product Z-test
Cited In (2)
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)
