LECTURES A GRATIS GLOBAL SERVICE
⌕ SEARCH GRATIS GLOBAL ↗
LECTURES
Interactive Proofs and the Sum-Check Protocol, Part 2
SOURCE: YOUTUBE · NO TRACKING UNTIL YOU PRESS PLAY · TROUBLE PLAYING? WATCH AT THE SOURCE ↗

Interactive Proofs and the Sum-Check Protocol, Part 2

66 MIN · EN · STATUS: [ STREAMING ]
RATE THIS
MIT · Advanced Topics in Cryptography · LECTURE 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.

At a glance

Lecture facts

Runtime compared with the other 507 Mathematics lectures
Runtime1 h 6 m
Compared with MathematicsShorter than 69%
This series

Advanced Topics in Cryptography

Every lecture in order, sized by its length.

  • Earlier lectures
  • This lecture
  • Still to come
Lecture 2 of 41 h 31 m before this · 5 h 13 m in total

More from this course

3 LECTURES
Interactive Proofs and the Sum-Check Protocol, Part 1

Interactive Proofs and the Sum-Check Protocol, Part 1

MIT · 91 MIN
Doubly Efficient Interactive Proofs, Part 1

Doubly Efficient Interactive Proofs, Part 1

MIT · 113 MIN
Doubly Efficient Interactive Proofs, Part 2

Doubly Efficient Interactive Proofs, Part 2

MIT · 43 MIN