5 papers
From Coupling to Spectral Independence and Blackbox Comparison with the Down-Up Walk
Kuikui Liu
We show that the existence of a "good"' coupling w.r.t. Hamming distance for any local Markov chain on a discrete product space implies rapid mixing of the Glauber dynamics in a bl…
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 III: Mason's Ultra-Log-Concavity Conjecture for Independent Sets of Matroids
Nima Anari, Kuikui Liu, Shayan Oveis Gharan +1
We give a self-contained proof of the strongest version of Mason's conjecture, namely that for any matroid the sequence of the number of independent sets of given sizes is ultra lo…
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…