4 papers · 1 filter
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…
Improved Mixing of Critical Hardcore Model
Zongchen Chen, Tianhui Jiang
The hardcore model is one of the most classic and widely studied examples of undirected graphical models. Given a graph , the hardcore model describes a Gibbs distribution of $λ…
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…