8 papers · 1 filter
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…
Edge-Tilting Field Dynamics: Rapid Mixing at the Uniqueness Threshold and Optimal Mixing for Swendsen-Wang Dynamics
Xiaoyu Chen, Zhe Ju, Tianshun Miao +2
We prove two results on the mixing times of Markov chains for two-spin systems. First, we show that the Glauber dynamics mixes in polynomial time for the Gibbs distributions of ant…
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…
Efficient Parallel Ising Samplers via Localization Schemes
Xiaoyu Chen, Hongyang Liu, Yitong Yin +1
We introduce efficient parallel algorithms for sampling from the Gibbs distribution and estimating the partition function of Ising models. These algorithms achieve parallel efficie…
Faster Mixing of the Jerrum-Sinclair Chain
Xiaoyu Chen, Weiming Feng, Zhe Ju +3
We show that the Jerrum-Sinclair Markov chain on matchings mixes in time on any graph with vertices, edges, and maximum degree , for any constant…
Rapid Mixing on Random Regular Graphs beyond Uniqueness
Xiaoyu Chen, Zejia Chen, Zongchen Chen +2
The hardcore model is a fundamental probabilistic model extensively studied in statistical physics, probability theory, and computer science. For graphs of maximum degree , a we…