Sign inSign in

Interactive proofs

A proof system where a prover and a verifier interact to establish the truth of a statement.
as Silvio Micali defines itMITThe wording closest to all 5 definitions
Watch it explained

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.

Lecturers

4

Each in their own terms, from the easiest level.

  • Ryan O'Donnell

    Carnegie Mellon University · Undergraduate

    A generalization of proof systems where the prover and verifier can interact over multiple rounds in polynomial time.
    • 9:41Interactive Proofs: IP=PSPACE
    • 1:17IP = PSPACE
  • Michael Sipser

    MIT · Undergraduate

    A probabilistic version of NP where a prover and a verifier interact through a randomized protocol to establish membership in a language.
    • 10:10Interactive Proof Systems, IP
  • Yael Tauman Kalai & Daniele Micciancio

    Ruhr University Bochum · Research

    A proof model based on a conversation between a prover and a verifier rather than a traditional static mathematical verification.
    • 4:47Cryptographic Proofs, Lattices & Hardness Assumptions: A Polylogue

Lectures that assume it

7

Connections

20

The lectures that define it or assume it, and the concepts next to it.

4 lecturers. Definitions are written by AI from each lecture’s transcript. A time with a play mark starts the lecture at the moment the lecturer says it.