5 papers · 1 filter
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…