ConceptTheory & Algos
Valiant-Vazirani theorem
A randomized reduction showing that solving Unique SAT is as hard as solving general SAT, meaning there exists a randomized reduction from SAT to Unique SAT with one-sided error.
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.
Randomized reduction2SAT2Unique SAT2Circuit SAT1Circuit satisfiability (SAT)1Complexity theory1Hashing1NP1
Lecturers
1Ryan O'Donnell
Connections
7The lectures that define it or assume it, and the concepts next to it.