The PCP theorem by gap amplification

DOI10.1145/1132516.1132553MaRDI QIDQ5891922zbMATH OpenOpenAlexFDO

Authors Irit Dinur

Publication date 25 November 2014

Published in Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1132516.1132553

zbMATH Keywords

gap amplificationPCP

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) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• The PCP theorem by gap amplification
• Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem
• A PCP characterization of NP with optimal amortized query complexity
• Gap Amplification in PCPs Using Lazy Random Walks
• A Combinatorial Consistency Lemma with Application to Proving the PCP Theorem

Cited in

(27)

• The commuting local Hamiltonian problem on locally expanding graphs is approximable in \(\mathsf{NP}\)
• ZK-PCPs from leakage-resilient secret sharing
• Combinatorial algorithms for distributed graph coloring
• The PCP theorem for NP over the reals
• On the derandomization of the graph test for homomorphism over groups
• Combinatorial PCPs with short proofs
• On a class of optimization problems with no ``efficiently computable solution
• Making the best of a leaky situation: zero-knowledge PCPs from leakage-resilient circuits
• Logical strength of complexity theory and a formalization of the PCP theorem in bounded arithmetic
• A PCP characterization of AM
• Short locally testable codes and proofs
• Bravely, moderately: a common theme in four recent works
• Gap Amplification in PCPs Using Lazy Random Walks
• The tensor product of two good codes is not necessarily robustly testable
• On the rectangle method in proofs of robustness of tensor products
• Combinatorial PCPs with efficient verifiers
• A Combinatorial Consistency Lemma with Application to Proving the PCP Theorem
• Imperfect gaps in Gap-ETH and PCPs
• Bridging a Small Gap in the Gap Amplification of Assignment Testers
• Cones of multipowers and combinatorial optimization problems
• Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem
• The PCP theorem by gap amplification
• Mathematics of computation through the lens of linear equations and lattices
• Derandomized parallel repetition via structured PCPs
• Quantum interactive oracle proofs
• A new line of attack on the dichotomy conjecture
• Challenging epistemology: Interactive proofs and zero knowledge

This page was built for publication: The PCP theorem by gap amplification

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