Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem

DOI10.1137/S0097539705446962MaRDI QIDQ5757456zbMATH OpenOpenAlexFDO

Authors Irit Dinur, Omer Reingold

Publication date 7 September 2007

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0097539705446962

zbMATH Keywords

combinatorial proofPCP theoremassignment tester

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• The PCP theorem by gap amplification
• The PCP theorem by gap amplification
• A Combinatorial Consistency Lemma with Application to Proving the PCP Theorem
• Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
• Combinatorial PCPs with short proofs

Cited in

(69)

• PCPs and the hardness of generating synthetic data
• An exponential separation between \textsf{MA} and \textsf{AM} proofs of proximity
• Robustly self-ordered graphs: constructions and applications to property testing
• Universal locally verifiable codes and 3-round interactive proofs of proximity for CSP
• Combinatorial PCPs with short proofs
• On the (In)security of Kilian-based SNARGs
• Combinatorial algorithms for distributed graph coloring
• Erasure-Resilient Property Testing
• Short PCPPs verifiable in polylogarithmic time with \(O(1)\) queries
• Towards lower bounds on locally testable codes via density arguments
• On Dinur’s proof of the PCP theorem
• Bridging a Small Gap in the Gap Amplification of Assignment Testers
• Derandomized parallel repetition via structured PCPs
• From local to robust testing via agreement testing
• Cube vs. Cube Low Degree Test.
• The PCP theorem by gap amplification
• scientific article; zbMATH DE number 7650107 (Why is no real title available?)
• Proofs of proximity for context-free languages and read-once branching programs
• Combinatorial algorithms for distributed graph coloring
• Non-interactive proofs of proximity
• Short locally testable codes and proofs: a survey in two parts
• Composition of low-error 2-query PCPs using decodable PCPs
• The tensor product of two good codes is not necessarily robustly testable
• On the rectangle method in proofs of robustness of tensor products
• A combination of testability and decodability by tensor products
• Efficient Probabilistically Checkable Debates
• Erasures versus errors in local decoding and property testing
• Direct sum testing
• Proofs of proximity for context-free languages and read-once branching programs
• Relaxed locally correctable codes
• Smooth and strong PCPs
• Arguments of proximity (extended abstract)
• Local proofs approaching the witness length
• Revisiting alphabet reduction in Dinur’s PCP.
• Probabilistic checking against non-signaling strategies from linearity testing
• ZK-PCPs from leakage-resilient secret sharing
• An exponential separation between MA and AM proofs of proximity
• Relaxed locally correctable codes
• A PCP characterization of AM
• The PCP theorem by gap amplification
• Erasures vs. errors in local decoding and property testing
• Quasi-linear size zero knowledge from linear-algebraic PCPs
• Short locally testable codes and proofs
• Computational integrity with a public random string from quasi-linear PCPs
• Towards a proof of the 2-to-1 games conjecture
• \textsc{Fractal}: post-quantum and transparent recursive proofs from holography
• A combinatorial characterization of smooth LTCs and applications
• On axis-parallel tests for tensor product codes
• Combinatorial PCPs with efficient verifiers
• Alphabet reduction for reconfiguration problems
• Invariance in property testing
• Constant-round interactive proofs for delegating computation
• Rigid matrices from rectangular PCPs
• Composition of semi-LTCs by two-wise tensor products
• Shorter arithmetization of nondeterministic computations
• A PCP theorem for interactive proofs and applications
• From Local to Robust Testing via Agreement Testing
• Parameterized inapproximability hypothesis under ETH
• Hardness self-amplification: simplified, optimized, and unified
• On approximability of satisfiable k-CSPs. III
• Brief announcement: Erasure-resilience versus tolerance to errors
• On axis-parallel tests for tensor product codes
• Low-degree test with polynomially small error
• Proving as fast as computing: succinct arguments with constant prover overhead
• Explicit strong LTCs with inverse poly-log rate and constant soundness
• Efficient multivariate low-degree tests via interactive oracle proofs of proximity for polynomial codes
• Lower bounds against sparse symmetric functions of ACC circuits: expanding the reach of \#SAT algorithms
• Bravely, moderately: a common theme in four recent works
• Limitation on the Rate of Families of Locally Testable Codes

This page was built for publication: Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem

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