Exact Complexity of NP-Complete Problems and Consequences
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.