LECTURES A GRATIS GLOBAL SERVICE
⌕ SEARCH GRATIS GLOBAL ↗
LECTURES
PCP via GKR and Interactive Arguments, Part 1
SOURCE: YOUTUBE · NO TRACKING UNTIL YOU PRESS PLAY · TROUBLE PLAYING? WATCH AT THE SOURCE ↗

PCP via GKR and Interactive Arguments, Part 1

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

Yael T. Kalai lectures on probabilistically checkable proofs (PCPs) as part of MIT's 6.5630 Advanced Topics in Cryptography course from Fall 2023. She covers the formal definition of PCPs and walks through their construction via the GKR (Goldwasser-Kalai-Rothblum) protocol, then moves into interactive succinct arguments for NP. The lecture is technical and proof-driven, aimed at students who already have background in complexity theory and cryptographic protocols, building toward the succinct argument systems that underlie modern zero-knowledge proof constructions. As Part 1 of a two-part treatment, it lays the theoretical groundwork, with Kalai working through definitions and constructions on the board in the style of a graduate seminar. Part of MIT OpenCourseWare's published lecture series for the course, released under a Creative Commons license.

At a glance

Lecture facts

Runtime compared with the other 734 Mathematics lectures
Runtime1 h 30 m
Compared with MathematicsLonger than 91%
This series

Advanced Topics in Cryptography

Every lecture in order, sized by its length.

  • Earlier lectures
  • This lecture
  • Still to come
Lecture 6 of 166 h 35 m before this · 21 h 39 m in total

More from this course

12 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
Doubly Efficient Interactive Proofs, Part 2

Doubly Efficient Interactive Proofs, Part 2

MIT · 43 MIN
Continuation of the GKR Protocol and Corollaries

Continuation of the GKR Protocol and Corollaries

MIT · 82 MIN
PCP via GKR and Interactive Arguments, Part 2

PCP via GKR and Interactive Arguments, Part 2

MIT · 71 MIN
The Kilian-Micali Protocol, Part 1

The Kilian-Micali Protocol, Part 1

MIT · 105 MIN
Fiat-Shamir Paradigm and Zero-Knowledge Proofs, Part 1

Fiat-Shamir Paradigm and Zero-Knowledge Proofs, Part 1

MIT · 93 MIN
Lecture 6: Fiat-Shamir Paradigm and Zero-Knowledge Proofs, Part 2

Lecture 6: Fiat-Shamir Paradigm and Zero-Knowledge Proofs, Part 2

MIT · 69 MIN
Soundness of the Fiat-Shamir Paradigm in the Standard Model, Part 1

Soundness of the Fiat-Shamir Paradigm in the Standard Model, Part 1

MIT · 94 MIN
Soundness of the Fiat-Shamir Paradigm in the Standard Model, Part 2

Soundness of the Fiat-Shamir Paradigm in the Standard Model, Part 2

MIT · 65 MIN
Succinct Non-Interactive Arguments for Batch NP (BARGs) from LWE, Part 1

Succinct Non-Interactive Arguments for Batch NP (BARGs) from LWE, Part 1

MIT · 82 MIN