5 papers
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…
Counting and Sampling Labeled Chordal Graphs in Polynomial Time
Ursula Hebert-Johnson, Daniel Lokshtanov, Eric Vigoda
We present the first polynomial-time algorithm to exactly compute the number of labeled chordal graphs on vertices. Our algorithm solves a more general problem: given and $…
Optimal Mixing via Tensorization for Random Independent Sets on Arbitrary Trees
Charilaos Efthymiou, Thomas P. Hayes, Daniel Stefankovic +1
We study the mixing time of the single-site update Markov chain, known as the Glauber dynamics, for generating a random independent set of a tree. Our focus is obtaining optimal co…
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 h…
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…