scientific article; zbMATH DE number 1789920

MaRDI QIDQ4549231zbMATH OpenFDO

Authors Sanjeev Arora

Publication date 6 October 2002

zbMATH Keywords

approximation algorithmscomplexity theoryNPPCP theoremsprobabilistically checkable proofs

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) 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

• Probabilistically checkable proofs and their consequences for approximation algorithms
• Probabilistic checking of proofs
• scientific article; zbMATH DE number 1256636
• Interactive and probabilistic proof-checking
• scientific article; zbMATH DE number 1256635

Cited in

(3)

• Probabilistically checkable proofs and codes
• On Dinur’s proof of the PCP theorem
• Product-state approximations to quantum states

This page was built for publication:

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