Zeros of Holant Problems: Locations and Algorithms

Heng Guo, Chao Liao, Pinyan Lu, Chihao Zhang

Research output: Contribution to journalArticlepeer-review

Abstract / Description of output

We present fully polynomial-time (deterministic or randomised) approximation schemes for Holant problems, defined by a non-negative constraint function satisfying a generalised second order recurrence modulo a couple of exceptional cases. As a consequence, any non-negative Holant problem on cubic graphs has an efficient approximation algorithm unless the problem is equivalent to approximately counting perfect matchings, a central open problem in the area. This is in sharp contrast to the computational phase transition shown by 2-state spin systems on cubic graphs. Our main technique is the recently established connection between zeros of graph polynomials and approximate counting.
Original languageEnglish
Article number4
Number of pages25
JournalACM Transactions on Algorithms
Issue number1
Publication statusPublished - 31 Dec 2020

Keywords / Materials (for Non-textual outputs)

  • Approximate counting
  • zero-free region
  • Holant problem
  • holographic algorithms


Dive into the research topics of 'Zeros of Holant Problems: Locations and Algorithms'. Together they form a unique fingerprint.

Cite this