4 papers
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…
Deterministic counting from coupling independence
Xiaoyu Chen, Weiming Feng, Heng Guo +2
We show that spin systems with bounded degrees and coupling independence admit fully polynomial time approximation schemes (FPTAS). We design a new recursive deterministic counting…
Rapid Mixing via Coupling Independence for Spin Systems with Unbounded Degree
Xiaoyu Chen, Weiming Feng
We develop a new framework to prove the mixing or relaxation time for the Glauber dynamics on spin systems with unbounded degree. It works for general spin systems including both $…
Optimal Mixing for Randomly Sampling Edge Colorings on Trees Down to the Max Degree
Charlie Carlson, Xiaoyu Chen, Weiming Feng +1
We address the convergence rate of Markov chains for randomly generating an edge coloring of a given tree. Our focus is on the Glauber dynamics which updates the color at a randoml…