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.
The focus on (the negative side of) expressibility for approximate counting problems appears in @cite_4 , where logsupermodular functions are shown not to express non-logsupermodular functions in the context of @math s.
@cite_4
2010996873
We prove semi-logarithmic inapproximability for a maximization problem called unique coverage: given a collection of sets, find a subcollection that maximizes the number of elements covered exactly once. Specifically, we prove O(1 logσ(e)n) inapproximability assuming that NP n BPTIME(2ne) for some e > 0. We also prove O(1 log1 3-e n) inapproximability, for any e > 0, assuming that refuting random instances of 3SAT is hard on average; and prove O(1 log n) inapproximability under a plausible hypothesis concerning the hardness of another problem, balanced bipartite independent set. We establish matching upper bounds up to exponents, even for a more general (budgeted) setting, giving an Ω(1 log n)-approximation algorithm as well as an Ω(1 log B)-approximation algorithm when every set has at most B elements. We also show that our inapproximability results extend to envy-free pricing, an important problem in computational economics. We describe how the (budgeted) unique coverage problem, motivated by real-world applications, has close connections to other theoretical problems including max cut, maximum coverage, and radio broad-casting.