95 citations · 767 across the 72 of their papers we have counts for
Showing 2009Show all
2 papers · 1 filter
cs.CC2009★ 1 cited
The Complexity of Approximating Bounded-Degree Boolean \sharp CSP
Martin Dyer, Leslie Ann Goldberg, Markus Jalsenius +1
The degree of a CSP instance is the maximum number of times that any variable appears in the scopes of constraints. We consider the approximate counting problem for Boolean CSP wit…
cs.CC2009★ 26 cited
Inapproximability of the Tutte polynomial of a planar graph
Leslie Ann Goldberg, Mark Jerrum
The Tutte polynomial of a graph G is a two-variable polynomial T(G;x,y) that encodes many interesting properties of the graph. We study the complexity of the following problem, for…