Group:Complexity Group
Title: Which Problems Have Strongly Exponential Complexity
Speaker: Shiteng Chen Tsinghua university
Time: 2010-06-09 15:30-2010-06-09 17:00
Venue: FIT 1-222


Some of the natural problems (in the theory of NP-completeness and lower bounds for constant depth circuits) have been shown to have weakly exponential(2^(n^omega(1))) complexity, either absolutely or under a reasonable complexity assumption. But complexity of many such problems are believed to be strongly exponential(2^omega(n)).

The talk will present a paper by Impagliazzo, Paturi & Zane, which makes a progress towards closing the gap between weakly and strongly exponential bounds. They prove that, some of the NP-complete problems always need 2^omega(n) time to solve if 3SAT needs 2^omega(n) time. The main technical lemma in this paper is the sparsification lemma. It shows that, for any small epsilon, any k-CNF formula can be written as a disjunction of at most 2^epsilon*n sparse k-CNF formulas, each of them contain at most cn clauses for some constant c.

The paper is available here:

Short Bio: