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

Interactive Proofs and the Sum-Check Protocol, Part 1

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

At a glance

Lecture facts

Runtime compared with the other 507 Mathematics lectures
Runtime1 h 31 m
Compared with MathematicsLonger than 93%
This series

Advanced Topics in Cryptography

Every lecture in order, sized by its length.

  • Earlier lectures
  • This lecture
  • Still to come
Lecture 1 of 40 m before this · 5 h 13 m in total

More from this course

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

Interactive Proofs and the Sum-Check Protocol, Part 2

MIT · 66 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