
Interactive Proofs and the Sum-Check Protocol, Part 1
Yael Kalai opens MIT's 6.5630 Advanced Topics in Cryptography by laying out the formal definition of interactive proofs, the setup of a prover trying to convince a skeptical verifier of a claim without the verifier doing the full computation itself. The core of the session is the sum-check protocol, built up step by step as a mechanism for verifying claims about sums of multivariate polynomials over large domains. Kalai then applies the protocol to the counting problem #SAT, showing how an exponentially large counting question can be checked through a short interactive exchange. The lecture is blackboard and slide based, with Kalai working through definitions and proofs at the pace of a graduate seminar, pausing for student questions throughout. It assumes prior exposure to complexity theory and sets up the course's later material on probabilistically checkable proofs and succinct arguments.