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

Research output: Journal Article or Conference Article in JournalJournal articleResearchpeer-review

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) 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)
Original languageEnglish
JournalInformation and Computation
Volume261
Pages (from-to)265
Number of pages280
ISSN0890-5401
DOIs
Publication statusPublished - Aug 2018
Externally publishedYes

Keywords

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

Fingerprint

Dive into the research topics of 'Block interpolation: A framework for tight exponential-time counting complexity'. Together they form a unique fingerprint.

Cite this