Block interpolation: A framework for tight exponential-time counting complexity

摘要

We devise a framework for proving tight lower bounds under the counting exponentialtime hypothesis # ETHintroduced by Delletal.(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 nvertices and O(n) edges. As exemplary applications of this framework, we obtain tight lower bounds under # ETHfor 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 etal.(2016) [24]. (C) 2018 Elsevier Inc. All rights reserved.