ConceptTheory & Algos
Probabilistically checkable proofs
A type of proof system where a reviewer can verify a proof with high confidence by spot-checking only a constant number of symbols randomly.
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.
Circuit SAT1Graph 3-coloring1Interactive proof system1Mathematical proof1NP1Polynomial time reduction1Probabilistic verification1
Opens up
Concepts that name this one as a prerequisite.
Lecturers
2Each in their own terms, from the easiest level.
Avi Wigderson
A proof system where a non-interactive proof can be verified probabilistically by reading only a constant number of bits from the proof string.Ryan O'Donnell
Lectures that assume it
3Connections
14The lectures that define it or assume it, and the concepts next to it.