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: http://cseweb.ucsd.edu/~russell/ipz.pdf