Block Interpolation: A Framework for Tight Exponential-Time Counting Complexity

We devise a framework for proving tight lower bounds under the counting exponential-time hypothesis

$$\mathsf {\#ETH}$$

#

ETH

introduced by Dell et al. Our framework allows to convert many known

$$\mathsf {\#P}$$

#

P

-hardness results for counting problems into results of the following type: If the given problem admits an algorithm with running time

$$2^{o(n)}$$

2

o

(

n

)

on graphs with

$$n$$

n

vertices and

$$\mathcal {O}(n)$$

O

(

n

)

edges, then

$$\mathsf {\#ETH}$$

#

ETH

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.