A Combinatorial Consistency Lemma with Application to Proving the PCP Theorem

DOI10.1137/S0097539797315744zbMath0948.68084OpenAlexW2021413381WikidataQ124809456 ScholiaQ124809456MaRDI QIDQ4943860

Shmuel Safra, Oded Goldreich

Publication date: 19 March 2000

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

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

zbMATH Keywords

NPlow-degree testsprobabilistically checkable proofs (PCP)parallelization of probabilistic proof systems

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (10)

Cube vs. Cube Low Degree Test. ⋮ Low-degree test with polynomially small error ⋮ Unnamed Item ⋮ Derandomized parallel repetition via structured PCPs ⋮ Fast Reed-Solomon Interactive Oracle Proofs of Proximity ⋮ Combinatorial algorithms for distributed graph coloring ⋮ Unnamed Item ⋮ From Local to Robust Testing via Agreement Testing ⋮ Direct Sum Testing ⋮ Combinatorial PCPs with short proofs

This page was built for publication: A Combinatorial Consistency Lemma with Application to Proving the PCP Theorem