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

assignment testercombinatorial proofPCP theorem

Mathematics Subject Classification ID

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

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)

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

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)