ConceptTheory & Algos
Instance checker
A randomized polynomial-time algorithm that takes a purported circuit or program for a function or language and an input, and either computes the correct value on that input or identifies a bug.
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.
Interactive proofs2Complexity classes1Complexity theory1Graph isomorphism1Interactive proof system1Language1Languages and complements1Oracle1
Lecturers
1Ryan O'Donnell
Connections
6The lectures that define it or assume it, and the concepts next to it.