Inapproximability of the independent set polynomial in the complex plane
- Submitting institution
-
University of Oxford
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 12165
- Type
- D - Journal article
- DOI
-
10.1137/18M1184485
- Title of journal
- SIAM Journal on Computing
- Article number
- -
- First page
- STOC18
- Volume
- 49
- Issue
- 5
- ISSN
- 0097-5397
- Open access status
- Compliant
- Month of publication
- September
- Year of publication
- 2020
- 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
-
3
- Research group(s)
-
-
- Citation count
- 0
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- The independent set polynomial has applications in combinatorics and statistical physics (where it is called the partition function of the hard-core model). The computational problem of approximating this polynomial is important for complex parameters but existing results about the complexity of approximation are mostly restricted to the reals. This paper injects complex-analysis techniques into complexity theory to give the first inapproximability results in the complex plane, answering "Question 1" of Peters and Regts (Mich Math J, https://projecteuclid.org/euclid.mmj/1541667626). The conference version appeared in STOC'18, and was one of a handful of papers especially selected from STOC'18 for SICOMP.
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -