9 papers
Sampling Matchings in Near-linear Time
Tianshun Miao, Yitong Yin
For every fixed activity , we establish three results for the monomer--dimer model on an -vertex simple graph with edges and maximum degree . 1. Near-linear…
On the self-intersection time of non-backtracking random walks
Ferenc Bencs, Leslie Ann Goldberg, Matthew Jenssen +4
We study the self-intersection time of the non-backtracking random walk on connected undirected graphs. For every fixed we show that the expected self-intersection time i…
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…
Near-Optimal Parallel Approximate Counting via Sampling
David G. Harris, Vladimir Kolmogorov, Hongyang Liu +2
The computational equivalence between approximate counting and sampling is well established for polynomial-time algorithms. The most efficient general reduction from counting to sa…
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…
Rapid Mixing at the Uniqueness Threshold
Xiaoyu Chen, Zongchen Chen, Yitong Yin +1
Over the past decades, a fascinating computational phase transition has been identified in sampling from Gibbs distributions. Though, the computational complexity at the critical p…
Spectral Independence Beyond Total Influence on Trees and Related Graphs
Xiaoyu Chen, Xiongxin Yang, Yitong Yin +1
We study how to establish , a key concept in sampling, without relying on total influence bounds, by applying an of t…