Zeros of Holant Problems: Locations and Algorithms

Heng Guo, Chao Liao, Pinyan Lu, Chihao Zhang

Research output: Contribution to journalArticlepeer-review

Abstract

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
Volume17
Issue number1
DOIs
Publication statusPublished - 31 Dec 2020

Keywords

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

Fingerprint

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

Cite this