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

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

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

(13)

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

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)