Approximating Holant problems by winding

Understand

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.