We prove an optimal mixing time bound for the single-site update Markov chain known as
the Glauber dynamics or Gibbs sampling in a variety of settings. Our work presents an …

We extend the notion of spectral independence (introduced by Anari, Liu, and Oveis
Gharan) from the Boolean domain to general discrete domains. This property characterises …

The spectral independence approach of Anari et al.(2020) utilized recent results on high-
dimensional expanders of Alev and Lau (2020) and established rapid mixing of the Glauber …

Strong spatial mixing (SSM) is an important quantitative notion of correlation decay for Gibbs
distributions arising in statistical physics, probability theory, and theoretical computer …

A well-known conjecture in computer science and statistical physics is that Glauber
dynamics on the set of k-colorings of a graph G on n vertices with maximum degree Δ is …

We show that the natural Glauber dynamics mixes rapidly and generates a random proper
edge-coloring of a graph with maximum degree Δ whenever the number of colors is at least …

We study the hard-core (gas) model defined on independent sets of an input graph where
the independent sets are weighted by a parameter (aka fugacity) λ>0. For constant Δ, the …

We give a polynomial time deterministic approximation algorithm (an FPTAS) for counting
the number of q-colorings of a graph of maximum degree Delta, provided only that q≥ …

We give a fully polynomial-time approximation scheme (FPTAS) to count the number of
independent sets on almost every $\Delta $-regular bipartite graph if $\Delta\ge 53$. In the …

We prove that the single-site Glauber dynamics for sampling proper q-colorings mixes in O Δ
(n log n) time on line graphs with n vertices and maximum degree Δ when q>(1+ o (1)) Δ …