Probabilistically checkable proofs and codes

zbMATH Open1252.68139MaRDI QIDQ3096563FDOQ3096563

Authors: Irit Dinur 

Publication date: 11 November 2011

Full work available at URL: http://ebooks.worldscinet.com/ISBN/9789814324359/9789814324359_0013.html

Recommendations

• Locally testable codes and PCPs of almost-linear length
• Smooth and strong PCPs
• Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
• Simple PCPs with poly-log rate and query complexity
• scientific article; zbMATH DE number 1789920

zbMATH Keywords

locally testable codesPCPprobabilistically checkable proofs

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)

Cited In (11)

• A coding theoretic study of MLL proof nets
• On Dinur’s proof of the PCP theorem
• Title not available (Why is that?)
• Efficient Probabilistically Checkable Debates
• Proof-carrying data from arithmetized random oracles
• Short locally testable codes and proofs
• PCP characterizations of NP: toward a polynomially-small error-probability
• Title not available (Why is that?)
• Probabilistic relational verification for cryptographic implementations
• On the concrete efficiency of probabilistically-checkable proofs
• Probably bounded suboptimal heuristic search

This page was built for publication: Probabilistically checkable proofs and codes

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