From Local to Robust Testing via Agreement Testing

DOI10.4230/LIPICS.ITCS.2019.29OpenAlexW2937040716MaRDI QIDQ5090403FDOQ5090403

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

Publication date: 18 July 2022

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

Recommendations

• From local to robust testing via agreement testing
• Strict local testability with consensus equals regularity
• Strict local testability with consensus equals regularity, and other properties
• Robust and distributed hypothesis testing
• scientific article; zbMATH DE number 4086760
• On testing local hypotheses via local divergence
• Fast closed testing for exchangeable local tests
• scientific article; zbMATH DE number 7650374
• Local admissibility and local unbiasedness in hypothesis testing problems

zbMATH Keywords

robust testingaffine-invariant codeslifted codeslocal testingagreement testing

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Title not available (Why is that?)
• Proof verification and the hardness of approximation problems
• Probabilistic checking of proofs
• 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
• Robust Characterizations of Polynomials with Applications to Program Testing
• Some 3CNF Properties Are Hard to Test
• Algebraic property testing: the role of invariance
• Improved low-degree testing and its applications
• Composition of semi-LTCs by two-wise tensor products
• On Sums of Locally Testable Affine Invariant Properties
• New affine-invariant codes from lifting
• High-rate locally-correctable and locally-testable codes with sub-polynomial query complexity
• 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)

• Testing equality under the local broadcast model
• Title not available (Why is that?)

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 Q5090403)