Probabilistically Checkable Proofs - Part I

Explore the foundational concepts of Probabilistically Checkable Proofs in this 59-minute lecture by Prahladh Harsha from the Tata Institute of Fundamental Research. Delve into the intricacies of proof verification, randomized verifiers, and the statement of claims. Examine the process of rewriting proofs, breaking them down into subproblems, and understand various proof types. This talk, part of the Proofs, Consensus, and Decentralizing Society Boot Camp at the Simons Institute, provides a comprehensive introduction to the subject, offering valuable insights for those interested in theoretical computer science and cryptography.

Intro
Verify
Proof verifier
Randomized verifier
Statement of claim
Rewriting Proof
Subproblems
Proof Rewriting
Proof Types