Approximating Holant problems by winding
arXiv:1301.2880
Abstract
We give an FPRAS for Holant problems with parity constraints and not-all-equal constraints, a generalisation of the problem of counting sink-free-orientations. The approach combines a sampler for near-assignments of "windable" functions -- using the cycle-unwinding canonical paths technique of Jerrum and Sinclair -- with a bound on the weight of near-assignments. The proof generalises to a larger class of Holant problems; we characterise this class and show that it cannot be extended by expressibility reductions. We then ask whether windability is equivalent to expressibility by matchings circuits (an analogue of matchgates), and give a positive answer for functions of arity three.
Cited by in corpus (6)
- A Simple FPTAS for Counting Edge Covers
- Slow Mixing of Glauber Dynamics for the Six-Vertex Model in the Ordered Phases
- Zeros and approximations of Holant polynomials on the complex plane
- FPRAS via MCMC where it mixes torpidly (and very little effort)
- Zeros of Holant problems: locations and algorithms
- FPTAS for Weighted Fibonacci Gates and Its Applications