ConceptTheory & Algos
Unique games conjecture
A conjecture stating that for all delta, it is NP-hard to distinguish between Label-Cover instances where almost all constraints can be satisfied versus instances where at most a delta fraction can be satisfied, even when the projection constraints are bijections.
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.
NP-hardness3Constraint satisfaction problem2Bijection1Complexity theory1CSP1Label cover1Max-bisection1NP-completeness1
Opens up
Concepts that name this one as a prerequisite.
Lecturers
3Each in their own terms, from the easiest level.
Avi Wigderson
A conjecture stating that certain two-prover games are NP-complete to distinguish, which implies optimal hardness results for many approximation problems.Ryan O'Donnell
A conjecture stating that for all epsilon greater than zero, there is a large enough Q such that even given a 1-epsilon satisfiable instance of max-bisection, it is NP-hard to find an assignment satisfying even an epsilon fraction of the constraints.John Wright
A constraint satisfaction problem parameterized by a positive integer q where all allowed constraints are two-variable bijective constraints.
Lectures that assume it
2Connections
15The lectures that define it or assume it, and the concepts next to it.