Probabilistically checkable proofs and codes

MaRDI QIDQ3096563zbMATH OpenFDO

Authors Irit Dinur

Publication date 11 November 2011

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

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)

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

Cited in

(12)

• Short locally testable codes and proofs
• On the concrete efficiency of probabilistically-checkable proofs
• Probably bounded suboptimal heuristic search
• PCP characterizations of NP: toward a polynomially-small error-probability
• Smooth and strong PCPs
• scientific article; zbMATH DE number 2110618 (Why is no real title available?)
• Proof-carrying data from arithmetized random oracles
• A coding theoretic study of MLL proof nets
• Probabilistic relational verification for cryptographic implementations
• scientific article; zbMATH DE number 1559565 (Why is no real title available?)
• On Dinur’s proof of the PCP theorem
• Efficient Probabilistically Checkable Debates

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)