
PCP via GKR and Interactive Arguments, Part 1
Yael T. Kalai lectures on probabilistically checkable proofs (PCPs) as part of MIT's 6.5630 Advanced Topics in Cryptography course from Fall 2023. She covers the formal definition of PCPs and walks through their construction via the GKR (Goldwasser-Kalai-Rothblum) protocol, then moves into interactive succinct arguments for NP. The lecture is technical and proof-driven, aimed at students who already have background in complexity theory and cryptographic protocols, building toward the succinct argument systems that underlie modern zero-knowledge proof constructions. As Part 1 of a two-part treatment, it lays the theoretical groundwork, with Kalai working through definitions and constructions on the board in the style of a graduate seminar. Part of MIT OpenCourseWare's published lecture series for the course, released under a Creative Commons license.