Xiaoyu Chen

most citedDeterministic counting from coupling independence

1 citations · 1 across the 2 of their papers we have counts for

collaborators

Showing cs.DSShow all

3 papers · 1 filter

cs.DS2026

An $O (n^{3})$ -time FPRAS for the Permanent

Xiaoyu Chen, Heng Guo, Eric Vigoda +1

We give an FPRAS for the permanent of an $n \times n$ $0/1$ matrix with running time $O (n^{3})$ . Our algorithm extends to a strongly polynomial FPRAS for arbitrary nonnegat…

cs.DS2024★ 1 cited

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…

cs.DS2024

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 $…

An O(n3)-time FPRAS for the Permanent

Deterministic counting from coupling independence

Rapid Mixing via Coupling Independence for Spin Systems with Unbounded Degree

An $O (n^{3})$ -time FPRAS for the Permanent