ConceptTheory & Algos
PCP theorem
A theorem stating that approximating Max-E3Sat to within some constant factor strictly less than 1 is NP-hard.
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-hardness4Constraint satisfaction problem2NP-completeness2Probabilistically checkable proofs23-SAT1Approximation algorithm1Complexity classes P and NP1E3-Sat1
Opens up
Concepts that name this one as a prerequisite.
Lecturers
2Each in their own terms, from the easiest level.
Ryan O'Donnell
A theorem stating that it is NP-hard to distinguish whether a 3-coloring instance has an optimal assignment of 1 or at most for some universal constant .Avi Wigderson
A theorem providing an optimization dichotomy for constraint satisfaction problems concerning approximation.
Lectures that assume it
5Connections
22The lectures that define it or assume it, and the concepts next to it.
Concepts9
- Constraint satisfaction problem
- NP-completeness
- Probabilistically checkable proofs
- 3-SAT
- Badness amplification
- Badness amplification theorem