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