17 citations · 24 across the 7 of their papers we have counts for
7 papers · 1 filter
Strong spatial mixing for colorings on trees and its algorithmic applications
Zongchen Chen, Kuikui Liu, Nitya Mani +1
Strong spatial mixing (SSM) is an important quantitative notion of correlation decay for Gibbs distributions arising in statistical physics, probability theory, and theoretical com…
A Matrix Trickle-Down Theorem on Simplicial Complexes and Applications to Sampling Colorings
Dorna Abdolazimi, Kuikui Liu, Shayan Oveis Gharan
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 $q\…
Spectral Independence via Stability and Applications to Holant-Type Problems
Zongchen Chen, Kuikui Liu, Eric Vigoda
This paper formalizes connections between stability of polynomials and convergence rates of Markov Chain Monte Carlo (MCMC) algorithms. We prove that if a (multivariate) partition…
Rapid Mixing of Glauber Dynamics up to Uniqueness via Contraction
Zongchen Chen, Kuikui Liu, Eric Vigoda
For general antiferromagnetic 2-spin systems, including the hardcore model and the antiferromagnetic Ising model, there is an for the partition function on graphs…
Log-Concave Polynomials IV: Approximate Exchange, Tight Mixing Times, and Near-Optimal Sampling of Forests
Nima Anari, Kuikui Liu, Shayan Oveis Gharan +2
We prove tight mixing time bounds for natural random walks on bases of matroids, determinantal distributions, and more generally distributions associated with log-concave polynomia…
Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model
Nima Anari, Kuikui Liu, Shayan Oveis Gharan
We say a probability distribution is spectrally independent if an associated correlation matrix has a bounded largest eigenvalue for the distribution and all of its conditional…
Log-Concave Polynomials II: High-Dimensional Walks and an FPRAS for Counting Bases of a Matroid
Nima Anari, Kuikui Liu, Shayan Oveis Gharan +1
We design an FPRAS to count the number of bases of any matroid given by an independent set oracle, and to estimate the partition function of the random cluster model of any matroid…