124 citations · 239 across the 28 of their papers we have counts for
Showing 2016Show all
3 papers · 1 filter
cs.CC2016
Implementations and the independent set polynomial below the Shearer threshold
Andreas Galanis, Leslie Ann Goldberg, Daniel Stefankovic
The independent set polynomial is important in many areas. For every integer , the Shearer threshold is the value . It is known that for $λ< - λ^*…
cs.DS2016
Approximating partition functions of bounded-degree Boolean counting Constraint Satisfaction Problems
Andreas Galanis, Leslie Ann Goldberg, Kuan Yang
We study the complexity of approximate counting Constraint Satisfaction Problems (#CSPs) in a bounded degree setting. Specifically, given a Boolean constraint language and a de…
cs.CC2016
A complexity trichotomy for approximately counting list H-colourings
Andreas Galanis, Leslie Ann Goldberg, Mark Jerrum
We examine the computational complexity of approximately counting the list H-colourings of a graph. We discover a natural graph-theoretic trichotomy based on the structure of the g…