Approximating Holant problems by winding
classification
💻 cs.CC
cs.DMmath.CO
keywords
holantproblemsclassconstraintsexpressibilityfunctionsgivenear-assignments
read the original 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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.