18 citations · 50 across the 17 of their papers we have counts for
21 papers
Fast Mixing for Low-Temperature Potts Models via Poisson Trees
Zongchen Chen, Andreas Galanis, Leslie Ann Goldberg +3
The -state ferromagnetic Potts model on a graph is a probability distribution on all -colourings of that favours many monochromatic edges. Approximate sampling from t…
Combinatorial Approach for Factorization of Variance and Entropy in Spin Systems
Zongchen Chen
We present a simple combinatorial framework for establishing approximate tensorization of variance and entropy in the setting of spin systems (a.k.a. undirected graphical models) b…
Spectral Independence and Local-to-Global Techniques for Optimal Mixing of Markov Chains
Zongchen Chen, Daniel Stefankovic, Eric Vigoda
This monograph is an exposition on an exciting new technique known as spectral independence, which has been instrumental in analyzing the convergence rate of Markov Chain Monte Car…
Fast Sampling of -Matchings and -Edge Covers
Zongchen Chen, Yuzhou Gu
For an integer , a -matching (resp. -edge cover) of a graph is a subset of edges such that every vertex is incident with at most (resp. at l…
Strong spatial mixing for colorings on trees and its algorithmic applications
Zongchen Chen, Kuikui Liu, Nitya Mani +1
Strong spatial mixing (SSM) is an important quantitative notion of correlation decay for Gibbs distributions arising in statistical physics, probability theory, and theoretical com…
From algorithms to connectivity and back: finding a giant component in random k-SAT
Zongchen Chen, Nitya Mani, Ankur Moitra
We take an algorithmic approach to studying the solution space geometry of relatively sparse random and bounded degree -CNFs for large . In the course of doing so, we establi…
Complexity of High-Dimensional Identity Testing with Coordinate Conditional Sampling
Antonio Blanca, Zongchen Chen, Daniel Štefankovič +1
We study the identity testing problem for high-dimensional distributions. Given as input an explicit distribution , an , and access to sampling oracle(s) for a hi…
Almost-Linear Planted Cliques Elude the Metropolis Process
Zongchen Chen, Elchanan Mossel, Ilias Zadik
A seminal work of Jerrum (1992) showed that large cliques elude the Metropolis process. More specifically, Jerrum showed that the Metropolis algorithm cannot find a clique of size…
Spectral Independence via Stability and Applications to Holant-Type Problems
Zongchen Chen, Kuikui Liu, Eric Vigoda
This paper formalizes connections between stability of polynomials and convergence rates of Markov Chain Monte Carlo (MCMC) algorithms. We prove that if a (multivariate) partition…
Sampling Colorings and Independent Sets of Random Regular Bipartite Graphs in the Non-Uniqueness Region
Zongchen Chen, Andreas Galanis, Daniel Štefankovič +1
For spin systems, such as the -colorings and independent-set models, approximating the partition function in the so-called non-uniqueness region, where the model exhibits long-r…
On Mixing of Markov Chains: Coupling, Spectral Independence, and Entropy Factorization
Antonio Blanca, Pietro Caputo, Zongchen Chen +3
For general spin systems, we prove that a contractive coupling for any local Markov chain implies optimal bounds on the mixing time and the modified log-Sobolev constant for a larg…
Optimal Mixing of Glauber Dynamics: Entropy Factorization via High-Dimensional Expansion
Zongchen Chen, Kuikui Liu, Eric Vigoda
We prove an optimal mixing time bound on the single-site update Markov chain known as the Glauber dynamics or Gibbs sampling in a variety of settings. Our work presents an improved…
Rapid Mixing for Colorings via Spectral Independence
Zongchen Chen, Andreas Galanis, Daniel Štefankovič +1
The spectral independence approach of Anari et al. (2020) utilized recent results on high-dimensional expanders of Alev and Lau (2020) and established rapid mixing of the Glauber d…
The Swendsen-Wang Dynamics on Trees
Antonio Blanca, Zongchen Chen, Daniel Štefankovič +1
The Swendsen-Wang algorithm is a sophisticated, widely-used Markov chain for sampling from the Gibbs distribution for the ferromagnetic Ising and Potts models. This chain has prove…
Hardness of Identity Testing for Restricted Boltzmann Machines and Potts models
Antonio Blanca, Zongchen Chen, Daniel Štefankovič +1
We study identity testing for restricted Boltzmann machines (RBMs), and more generally for undirected graphical models. Given sample access to the Gibbs distribution corresponding…
Rapid Mixing of Glauber Dynamics up to Uniqueness via Contraction
Zongchen Chen, Kuikui Liu, Eric Vigoda
For general antiferromagnetic 2-spin systems, including the hardcore model and the antiferromagnetic Ising model, there is an for the partition function on graphs…
Optimal Convergence Rate of Hamiltonian Monte Carlo for Strongly Logconcave Distributions
Zongchen Chen, Santosh S. Vempala
We study Hamiltonian Monte Carlo (HMC) for sampling from a strongly logconcave density proportional to where is -strongly convex and …
Lower bounds for testing graphical models: colorings and antiferromagnetic Ising models
Ivona Bezakova, Antonio Blanca, Zongchen Chen +2
We study the identity testing problem in the context of spin systems or undirected graphical models, where it takes the following form: given the parameter specification of the mod…
Fast algorithms at low temperatures via Markov chains
Zongchen Chen, Andreas Galanis, Leslie Ann Goldberg +3
We define a discrete-time Markov chain for abstract polymer models and show that under sufficient decay of the polymer weights, this chain mixes rapidly. We apply this Markov chain…
Swendsen-Wang Dynamics for General Graphs in the Tree Uniqueness Region
Antonio Blanca, Zongchen Chen, Eric Vigoda
The Swendsen-Wang dynamics is a popular algorithm for sampling from the Gibbs distribution for the ferromagnetic Ising model on a graph . The dynamics is a "global" Markov…
Structure Learning of -colorings
Antonio Blanca, Zongchen Chen, Daniel Štefankovič +1
We study the structure learning problem for -colorings, an important class of Markov random fields that capture key combinatorial structures on graphs, including proper coloring…