PCP characterizations of NP: toward a polynomially-small error-probability

DOI10.1007/s00037-011-0014-4zbMath1234.68133OpenAlexW1992067909MaRDI QIDQ649097

Irit Dinur, Eldar Fischer, Guy Kindler, Ran Raz, Shmuel Safra

Publication date: 30 November 2011

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00037-011-0014-4

zbMATH Keywords

PCPNPconsistent-readerlow-degree extensionrepresentation-proceduresum-check

Mathematics Subject Classification ID

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

Related Items (11)

Quantum information and the PCP theorem ⋮ Low-degree test with polynomially small error ⋮ PCPs via the low-degree long code and hardness for constrained hypergraph coloring ⋮ Approximation and hardness results for label cut and related problems ⋮ Mathematics of computation through the lens of linear equations and lattices ⋮ Derandomized parallel repetition via structured PCPs ⋮ PCP characterizations of NP: toward a polynomially-small error-probability ⋮ ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network ⋮ Smooth and strong PCPs ⋮ Three-Player Entangled XOR Games are NP-Hard to Approximate ⋮ On the hardness of approximating the min-hack problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• PCP characterizations of NP: toward a polynomially-small error-probability
• Non-deterministic exponential time has two-prover interactive protocols
• A well-characterized approximation problem
• Proof verification and the hardness of approximation problems
• Probabilistic checking of proofs
• On the hardness of approximating minimization problems
• A Parallel Repetition Theorem

This page was built for publication: PCP characterizations of NP: toward a polynomially-small error-probability