We characterize the uniqueness condition in the hardcore model for bipartite graphs with
degree bounds only on one side, and provide a nearly linear time sampling algorithm that …

We give a new rapid mixing result for a natural random walk on the independent sets of a
graph $ G $. We show that when $ G $ has bounded treewidth, this random walk--known as …

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 k= b (1+ ob (1))/ln b …

Abstract The Swendsen–Wang algorithm is a sophisticated, widely‐used Markov chain for
sampling from the Gibbs distribution for the ferromagnetic Ising and Potts models. This chain …

We study the mixing time of the single-site update Markov chain, known as the Glauber
dynamics, for generating a random independent set of a tree. Our focus is obtaining optimal …

A key insight from statistical physics about spin systems on random graphs is the central role
played by Gibbs measures on trees. We determine the local weak limit of the hardcore …

We study how to establish $\textit {spectral independence} $, a key concept in sampling,
without relying on total influence bounds, by applying an $\textit {approximate inverse} $ of …

For a sequence of Boolean functions $ f_n:\{-1, 1\}^{V_n}\longrightarrow\{-1, 1\} $, with
random input given by some probability measure $\mathbb {P} _n $, we say that there is …

As the penetration of wireless networks increase, number of neighboring networks
contending for the limited unlicensed spectrum band increases. This interference between …

We prove that, unless P= NP, there is no polynomial-time algorithm to approximate within
some multiplicative constant the average size of an independent set in graphs of maximum …