scientific article; zbMATH DE number 1789920

zbMATH Open1001.68049MaRDI QIDQ4549231FDOQ4549231

Authors: Sanjeev Arora 

Publication date: 6 October 2002

Title of this publication is not available (Why is that?)

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

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)

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)