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

DOI10.1007/S00037-011-0014-4MaRDI QIDQ649097zbMATH OpenOpenAlexFDO

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)

Copyright license Creative Commons Attribution-NonCommercial 4.0 International

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)

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

Cites work

• scientific article; zbMATH DE number 1222561 (Why is no real title available?)
• scientific article; zbMATH DE number 1559563 (Why is no real title available?)
• scientific article; zbMATH DE number 1559564 (Why is no real title available?)
• A Parallel Repetition Theorem
• A well-characterized approximation problem
• Non-deterministic exponential time has two-prover interactive protocols
• On the hardness of approximating minimization problems
• PCP characterizations of NP: toward a polynomially-small error-probability
• Probabilistic checking of proofs
• Proof verification and the hardness of approximation problems

Cited in

(13)

• scientific article; zbMATH DE number 1559563 (Why is no real title available?)
• On the hardness of approximating the min-hack problem
• Derandomized parallel repetition via structured PCPs
• ETH-hardness of approximating 2-CSPs and directed Steiner network
• 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
• Three-player entangled XOR games are NP-hard to approximate
• Low-degree test with polynomially small error
• PCP characterizations of NP: towards a polynomially-small error-probability
• 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)