Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6873778 | Information and Computation | 2018 | 16 Pages |
Abstract
We devise a framework for proving tight lower bounds under the counting exponential-time hypothesis #ETH introduced by Dell et al. (2014) [18]. Our framework allows us to convert classical #P-hardness results for counting problems into tight lower bounds under #ETH, thus ruling out algorithms with running time 2o(n) on graphs with n vertices and O(n) edges. As exemplary applications of this framework, we obtain tight lower bounds under #ETH for the evaluation of the zero-one permanent, the matching polynomial, and the Tutte polynomial on all non-easy points except for one line. This remaining line was settled very recently by Brand et al. (2016) [24].
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Radu Curticapean,