Janne H. Korhonen: Lower bounds from the strong exponential time hypothesis

Practicalities

Lunch is served at 12:00 noon (register at this doodle by Wednesday April 23 at 8 pm). The presentation starts at 12:10 pm and ends at 1 pm. Those of us who wish reconvene after a short break for ca two hours of more technical discussions.

Abstract

Exact exponential algorithmics considers the development of faster, still exponential-time, algorithms for problems that are believed to lie outside polynomial time. There have been notable successes in the recent years, such as the Björklund's 1.657^n time Hamiltonian path algorithm; however, for the central problem of CNF-SAT, no such strictly exponential improvement has been obtained. That is, while o(2^n) algorithms are known, there is no known algorithm with running time c^n poly(n,m) for some c < 2.

Following the influential work of Impagliazzo, Paturi and Zane, connections between the exponential complexity of CNF-SAT and other problems have been investigated extensively. The basic idea is that if we assume CNF-SAT in fact cannot be solved in time c^n poly(n,m) for any c < 2 -- this assumption is known as the strong exponential time hypothesis -- we can then derive conditional lower bounds for other problems. These results can then be viewed as hardness results or new attacks on the complexity of CNF-SAT, depending on one's view on the strong exponential time hypothesis.

In this talk, we will survey these connections between the strong exponential time hypothesis and other problems. In particular, we will focus on the perhaps somewhat unexpected conditional lower bounds for polynomial-time problems, and the basic strategies used in the proofs of these results.