PCP characterizations of NP: toward a polynomially-small error-probability
From MaRDI portal
Publication:649097
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
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
