
PCP via GKR and Interactive Arguments, Part 2
Yael T. Kalai continues her MIT course 6.5630, Advanced Topics in Cryptography, with the second half of a lecture on probabilistically checkable proofs. She returns to the definition of PCPs and works through their construction via the GKR protocol, then develops an interactive succinct argument system for NP. The seventy one minute session builds on prior lectures' groundwork in interactive proofs, walking through the formal machinery that lets a verifier check a proof by reading only a few bits of it. Kalai works at the board, developing definitions and proof steps in sequence for a graduate audience already versed in complexity theory and cryptographic proof systems. The lecture is part of MIT OpenCourseWare's Fall 2023 offering of 6.5630, aimed at students studying succinct arguments and their role in modern cryptographic protocol design.