activity
20092013
most citedImproved Inapproximability Results for Counting Independent Sets in the Hard-Core Model

20 citations · 45 across the 6 of their papers we have counts for

collaborators

6 papers

cs.CC2013★ 1 cited

Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results

Andreas Galanis, Daniel Stefankovic, Eric Vigoda +1

Recent results establish for 2-spin antiferromagnetic systems that the computational complexity of approximating the partition function on graphs of maximum degree D undergoes a ph…

cs.DM2013★ 1 cited

Improved Bounds on the Phase Transition for the Hard-Core Model in 2-Dimensions

Juan C. Vera, Eric Vigoda, Linji Yang

For the hard-core lattice gas model defined on independent sets weighted by an activity , we study the critical activity for the uniqueness/non-uniqueness th…

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…

math.PR2010

Phase Transition for Glauber Dynamics for Independent Sets on Regular Trees

Ricardo Restrepo, Daniel Stefankovic, Juan C. Vera +2

We study the effect of boundary conditions on the relaxation time of the Glauber dynamics for the hard-core model on the tree. The hard-core model is defined on the set of independ…

math.PR2009★ 12 cited

Phase transition for the mixing time of the Glauber dynamics for coloring regular trees

Prasad Tetali, Juan C. Vera, Eric Vigoda +1

We prove that the mixing time of the Glauber dynamics for random k-colorings of the complete tree with branching factor b undergoes a phase transition at . Ou…