Tianshun Miao

collaborators

3 papers

cs.DS2026

Sampling Matchings in Near-linear Time

Tianshun Miao, Yitong Yin

For every fixed activity $λ > 0$ , we establish three results for the monomer--dimer model on an $n$ -vertex simple graph $G$ with $m \geq 1$ edges and maximum degree $Δ$ . 1. Near-linear…

cs.DS2026

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…

cs.DS2025

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 $O (Δ^{2} m)$ on any graph with $n$ vertices, $m$ edges, and maximum degree $Δ$ , for any constant…