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 # 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 2 o ( 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].

Authors

• Radu Curticapean

Keywords

• Exponential-time hypothesis
• Counting complexity
• Permanent
• Matching polynomial
• Independent set polynomial
• Tutte polynomial