2013/01/14 by Colin McQuillan, McQuillan, Colin · 1 citation
Computer Science · Economics, Econometrics and Finance · Mathematics · #Bayesian Modeling and Causal Inference #Combinatorics (math.CO) #Computational Complexity (cs.CC) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Game Theory and Voting Systems #Markov Chains and Monte Carlo Methods
paper · pdf · doi:10.48550/arxiv.1301.2880
openalex publication_date 2013/01/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.