Fine-grained dichotomies for the Tutte Plane and Boolean #CSP
- Submitting institution
-
University of Oxford
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 15923
- Type
- D - Journal article
- DOI
-
10.1007/s00453-018-0472-z
- Title of journal
- Algorithmica
- Article number
- -
- First page
- 541
- Volume
- 81
- Issue
- 2
- ISSN
- 0178-4617
- Open access status
- Deposit exception
- Month of publication
- June
- Year of publication
- 2018
- URL
-
-
- Supplementary information
-
-
- Request cross-referral to
- -
- Output has been delayed by COVID-19
- No
- COVID-19 affected output statement
- -
- Forensic science
- No
- Criminology
- No
- Interdisciplinary
- No
- Number of additional authors
-
2
- Research group(s)
-
-
- Citation count
- 0
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- The Tutte polynomial captures key problems across the disciplines of statistical physics, computer science, and combinatorics. Quantifying the complexity of evaluating this polynomial has been an important area of investigation in all three fields since the seminal paper of Jaeger, Vertigan, and Welsh in 1990. This paper, whose conference version received the Best Paper award at IPEC 2016, provides the final missing piece in the fine-grained analysis of its complexity. As a result, we now how have a complete understanding of all computational problems captured by the Tutte polynomial, under the well-known Exponential Time Hypothesis #ETH.
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -