We devise a framework for proving tight lower bounds under the counting exponential-time hypothesis
introduced by Dell et al. Our framework allows to convert many known
-hardness results for counting problems into results of the following type: If the given problem admits an algorithm with running time
on graphs with
fails. As exemplary applications of this framework, we obtain such tight lower bounds for the evaluation of the zero-one permanent, the matching polynomial, and the Tutte polynomial on all non-easy points except for two lines.
Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten