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

Doubly Efficient Interactive Proofs, Part 2

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

Yael Kalai continues MIT's graduate course 6.5630, Advanced Topics in Cryptography, with the second half of her treatment of doubly efficient interactive proofs. She works through the definition and a worked example, counting triangles in a graph, before introducing the low-degree extension technique used to compress verification. The lecture builds toward the GKR protocol, which gives doubly efficient interactive proofs for all bounded-depth computations, letting a weak verifier check a powerful prover's work on any computation expressible as a shallow circuit. The style is chalkboard-and-whiteboard proof construction aimed at students already fluent in complexity theory and cryptographic protocols, part of a 43-minute session that assumes the prior lecture's setup. It is a specialist talk, dense with notation, suited to viewers studying interactive proof systems and verifiable computation rather than a general audience.

At a glance

Lecture facts

Runtime compared with the other 507 Mathematics lectures
Runtime43 m
Compared with MathematicsShorter than 93%
This series

Advanced Topics in Cryptography

Every lecture in order, sized by its length.

  • Earlier lectures
  • This lecture
  • Still to come
Lecture 4 of 44 h 30 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 1

Doubly Efficient Interactive Proofs, Part 1

MIT · 113 MIN