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 2o(n) * poly(n) unless ETH fails. This lower bound is asymptotically tight because Ryser's formula counts the number of perfect matchings in time 2n * 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.