6 papers
An FPRAS for Counting Common Bases of Two Matroids
Xiaoyu Chen, Kuikui Liu
We design the first polynomial-time algorithms for approximately counting and almost uniformly sampling common bases of two matroids given by their independence oracles. Moreover,…
Spectral Gap of Down-Up Walks via Trickle-Down: A Simplified and Sharpened Analysis
Xiaoyu Chen, Kuikui Liu
Local-to-global techniques for establishing spectral gaps have played a central role in the modern theory of Markov chain mixing times and the theory of high-dimensional expanders.…
A Spectral Local-to-Global Principle for Spin Systems on Graphs with Girth At Least Five
Xiaoyu Chen, Kuikui Liu
It is proved that, for every , the Glauber dynamics for the uniform distribution on proper -colorings is rapidly mixing when and the underlying graph…
Subquadratic Counting via Perfect Marginal Sampling
Xiaoyu Chen, Zongchen Chen, Kuikui Liu +1
We study the computational complexity of approximately computing the partition function of a spin system. Techniques based on standard counting-to-sampling reductions yield $\tilde…
Locally Stationary Distributions: A Framework for Analyzing Slow-Mixing Markov Chains
Kuikui Liu, Sidhanth Mohanty, Prasad Raghavendra +2
Many natural Markov chains fail to mix to their stationary distribution in polynomially many steps. Often, this slow mixing is inevitable since it is computationally intractable to…
Fast Mixing in Sparse Random Ising Models
Kuikui Liu, Sidhanth Mohanty, Amit Rajaraman +1
Motivated by the community detection problem in Bayesian inference, as well as the recent explosion of interest in spin glasses from statistical physics, we study the classical Gla…