Exact Complexity of NP-Complete Problems and Consequences

Lecture 1: Satisfiability Algorithms I
Lecture 2: Satisfiability Algorithms II
Lecture 3: Sparsification Lemma and ETH
 

This series of talks was part of the Fine-Grained Complexity and Algorithm Design Boot Camp. Videos for each talk area available through the links above.

Speaker: Mohan Paturi, UC San Diego

I will survey the satisfiability algorithms for k-CNF and extensions and explore the connections to lower bounds for depth-3 circuits. I will also provide motivation for ETH and SETH and discuss the Sparsification Lemma.