20 citations · 45 across the 6 of their papers we have counts for
Showing 2011Show all
2 papers · 1 filter
cs.CC2011★ 20 cited
Improved Inapproximability Results for Counting Independent Sets in the Hard-Core Model
Andreas Galanis, Qi Ge, Daniel Stefankovic +2
We study the computational complexity of approximately counting the number of independent sets of a graph with maximum degree Delta. More generally, for an input graph G=(V,E) and…
math.PR2011★ 11 cited
Improved Mixing Condition on the Grid for Counting and Sampling Independent Sets
Ricardo Restrepo, Jinwoo Shin, Prasad Tetali +2
We study the hard-core model defined on independent sets, where each independent set I in a graph G is weighted proportionally to , for a positive real parameter . For…