24 citations · 60 across the 8 of their papers we have counts for
8 papers · 1 filter
Boolean approximate counting CSPs with weak conservativity, and implications for ferromagnetic two-spin
Miriam Backens, Andrei Bulatov, Leslie Ann Goldberg +2
We analyse the complexity of approximate counting constraint satisfactions problems , where is a set of nonnegative rational-valued funct…
Counting list matrix partitions of graphs
Andreas Göbel, Leslie Ann Goldberg, Colin McQuillan +2
Given a symmetric D*D matrix M over {0,1,*}, a list M-partition of a graph G is a partition of G's vertices into D parts associated with the rows of M. The part of each vertex is c…
Approximating Holant problems by winding
Colin McQuillan
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 combine…
Approximating the partition function of planar two-state spin systems
Leslie Ann Goldberg, Mark Jerrum, Colin McQuillan
We consider the problem of approximating the partition function of the hard-core model on planar graphs of degree at most 4. We show that when the activity lambda is sufficiently l…
The complexity of approximating conservative counting CSPs
Xi Chen, Martin Dyer, Leslie Ann Goldberg +4
We study the complexity of approximately solving the weighted counting constraint satisfaction problem #CSP(F). In the conservative case, where F contains all unary functions, ther…
Degree two approximate Boolean #CSPs with variable weights
Colin McQuillan
A counting constraint satisfaction problem (#CSP) asks for the number of ways to satisfy a given list of constraints, drawn from a fixed constraint language Γ. We study how hard it…
LSM is not generated by binary functions
Colin McQuillan
The material in this note is now superseded by arXiv:1108.5288v4. Bulatov et al. [1] defined the operation of (efficient) pps_ω-definability in order to study the computational com…
The expressibility of functions on the Boolean domain, with applications to Counting CSPs
Andrei A. Bulatov, Martin Dyer, Leslie Ann Goldberg +2
An important tool in the study of the complexity of Constraint Satisfaction Problems (CSPs) is the notion of a relational clone, which is the set of all relations expressible using…