# Computational Complexity - Research Seminar

## Holger Dell (HU Berlin): *Strongly Vertex-Exponential Lower Bounds for the 0,1-Permanent*

April 29, 2008, 10:15 a.m.

E 1 3, Room 415

We give background information on the exponential time hypothesis (ETH), subexponential parameterized complexity theory, and the sparsification lemma. Natural questions arise in this not yet

well-understood area, and in particular, almost nothing is known about the subexponential tractibility of counting problems. We show that the 0,1-permanent of an *n*×*n* matrix cannot be

evaluated in time 2^{o(n)} * poly(*n*) unless ETH fails. This lower bound is asymptotically tight because Ryser's formula counts the number of perfect matchings in time 2^{n} * poly(*n*). We obtain similar tight results for

the Tutte polynomial, which Björklund et al. (2007+) very recently proved to be

computable in vertex-exponential time.