scientific article; zbMATH DE number 1789920

MaRDI QIDQ4549231zbMATH OpenFDO

Authors Sanjeev Arora

Publication date 6 October 2002

zbMATH Keywords

approximation algorithmscomplexity theoryprobabilistically checkable proofsNPPCP theorems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

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)

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

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)