124 citations · 501 across the 39 of their papers we have counts for
53 papers
Fast FPRAS for the Permanent
Xiaoyu Chen, Heng Guo, Eric Vigoda +1
We give an FPRAS for the permanent of an matrix with running time . Our algorithm extends to a strongly polynomial FPRAS f…
Faster FPRAS for the Permanent via Restricted Poincaré Inequalities and Coupled Flows
Xiaoyu Chen, Eric Vigoda, Xiongxin Yang
The permanent of an matrix equals the number of perfect matchings in the bipartite graph with edges defined by . Jerrum, Sinclair, and Vigoda (2004) presen…
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 $…
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…
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 hi…