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

DOI10.1007/S00037-011-0014-4zbMATH Open1234.68133OpenAlexW1992067909MaRDI QIDQ649097FDOQ649097

Authors: 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

Recommendations

• PCP characterizations of NP: towards a polynomially-small error-probability
• scientific article; zbMATH DE number 1559563
• Probabilistic checking of proofs
• Probabilistically checkable proofs and codes
• scientific article; zbMATH DE number 1256635

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)

Cites Work

• Proof verification and the hardness of approximation problems
• Probabilistic checking of proofs
• Title not available (Why is that?)
• Non-deterministic exponential time has two-prover interactive protocols
• A well-characterized approximation problem
• On the hardness of approximating minimization problems
• A Parallel Repetition Theorem
• Title not available (Why is that?)
• PCP characterizations of NP: toward a polynomially-small error-probability
• Title not available (Why is that?)

Cited In (12)

• Title not available (Why is that?)
• On the hardness of approximating the min-hack problem
• Derandomized parallel repetition via structured PCPs
• Smooth and strong PCPs
• PCPs via the low-degree long code and hardness for constrained hypergraph coloring
• Mathematics of computation through the lens of linear equations and lattices
• PCP characterizations of NP: toward a polynomially-small error-probability
• Quantum information and the PCP theorem
• ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network
• Three-player entangled XOR games are NP-hard to approximate
• Low-degree test with polynomially small error
• Approximation and hardness results for label cut and related problems

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

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