
Interactive Proofs and the Sum-Check Protocol, Part 2
Yael T. Kalai continues MIT's 6.5630 Advanced Topics in Cryptography with the second part of her opening lecture on interactive proofs. She formalizes the definition of an interactive proof system, then works through the sum-check protocol in detail, showing how a verifier can check a claimed sum over a multivariate polynomial without evaluating it everywhere. The lecture closes by applying this machinery to build an interactive proof for counting satisfying assignments to a Boolean formula, the #SAT problem. The style is blackboard-driven, building definitions and proofs step by step rather than relying on slides, aimed at students who already have a background in theoretical computer science and complexity theory. It sets up the protocol-level reasoning that the rest of the course will build on for doubly efficient and probabilistically checkable proof systems.