ConceptTheory & Algos
Interactive proofs
A proof system where a prover and a verifier interact to establish the truth of a statement.
Know first
Named as a prerequisite by the lectures that define this. The number is how many say so. A grey one has no page yet.
NP2Proof system2Prover2Verifier2Arthur-Merlin games1Complexity classes1Complexity theory1Cryptography1
Opens up
Concepts that name this one as a prerequisite.
Zero-knowledge proofs3Instance checker2#SAT in IP protocol verification1AM1AM protocol1Arthur-Merlin1Arthur-Merlin (AM) and Merlin-Arthur (MA) classes1Arthur-Merlin (AM) class1Arthur-Merlin (AM) hierarchy1Constant-round interactive proofs1Constant-round interactive proofs (Merlin-Arthur proofs)1Delegating computation1
Lecturers
4Each in their own terms, from the easiest level.
Ryan O'Donnell
A generalization of proof systems where the prover and verifier can interact over multiple rounds in polynomial time.Michael Sipser
A probabilistic version of NP where a prover and a verifier interact through a randomized protocol to establish membership in a language.Yael Tauman Kalai & Daniele Micciancio
A proof model based on a conversation between a prover and a verifier rather than a traditional static mathematical verification.
Lectures that assume it
7Connections
20The lectures that define it or assume it, and the concepts next to it.