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)

• A coding theoretic study of MLL proof nets
• On Dinur’s proof of the PCP theorem
• scientific article; zbMATH DE number 1559565 (Why is no real title available?)
• Efficient Probabilistically Checkable Debates
• Smooth and strong PCPs
• Proof-carrying data from arithmetized random oracles
• Short locally testable codes and proofs
• PCP characterizations of NP: toward a polynomially-small error-probability
• scientific article; zbMATH DE number 2110618 (Why is no real title available?)
• 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)