LECTURES A GRATIS GLOBAL SERVICE
⌕ SEARCH GRATIS GLOBAL ↗
LECTURES
Doubly Efficient Interactive Proofs, Part 1
SOURCE: YOUTUBE · NO TRACKING UNTIL YOU PRESS PLAY · TROUBLE PLAYING? WATCH AT THE SOURCE ↗

Doubly Efficient Interactive Proofs, Part 1

113 MIN · EN · STATUS: [ STREAMING ]
RATE THIS
MIT · Advanced Topics in Cryptography · LECTURE 3

Yael T. Kalai teaches the second lecture of MIT's 6.5630 Advanced Topics in Cryptography, continuing the course's treatment of interactive proof systems. The session builds the definition of doubly efficient interactive proofs through the worked example of counting triangles in a graph, then introduces the low-degree extension technique used to compress verification. Kalai extends this machinery to the GKR protocol, which gives doubly efficient interactive proofs for any computation of bounded depth. The lecture is blackboard-driven and proof-heavy, aimed at students who already have a background in complexity theory and cryptographic protocols. At roughly two hours, it works through definitions, protocol construction, and soundness arguments in detail rather than summarizing results, consistent with MIT OpenCourseWare's standard graduate lecture format.

At a glance

Lecture facts

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

Advanced Topics in Cryptography

Every lecture in order, sized by its length.

  • Earlier lectures
  • This lecture
  • Still to come
Lecture 3 of 42 h 37 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
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 2

Doubly Efficient Interactive Proofs, Part 2

MIT · 43 MIN