Conference item
Inapproximability of the independent set polynomial in the complex plane
- Abstract:
-
We study the complexity of approximating the value of the independent set polynomial ZG(λ) of a graph G with maximum degree Δ when the activity λ is a complex number. When λ is real, the complexity picture is well-understood, and is captured by two real-valued thresholds λ* and λc, which depend on Δ and satisfy 0<λ*<λc. It is known that if λ is a real number in the interval (−λ*,λc) then there is an FPTAS for approximating ZG(λ) on graphs G with maximum degree at most Δ. On the other h...
Expand abstract
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Authors
Funding
Bibliographic Details
- Publisher:
- Association for Computing Machinery Publisher's website
- Host title:
- STOC 2018 Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing
- Journal:
- STOC 2018 TheoryFest Journal website
- Pages:
- 1234-1240
- Publication date:
- 2018-06-20
- Acceptance date:
- 2018-02-09
- DOI:
- ISBN:
- 9781450355599
Item Description
- Keywords:
- Pubs id:
-
pubs:824707
- UUID:
-
uuid:6de03289-cdb1-4b07-88db-6b4c0b8cb234
- Local pid:
- pubs:824707
- Source identifiers:
-
824707
- Deposit date:
- 2018-02-15
Terms of use
- Copyright holder:
- Bezáková et al
- Copyright date:
- 2018
- Notes:
-
Copyright © 2018 the authors. Publication rights licensed to the
Association for Computing Machinery. This is the accepted manuscript version of the paper. The final version is available online from ACM at: https://doi.org/10.1145/3188745.3188788
Metrics
If you are the owner of this record, you can report an update to it here: Report update to this record