1 citations · 1 across the 6 of their papers we have counts for
7 papers · 1 filter
An -Time Sampler for Zero-Field Ferromagnetic Ising Models
Weiming Feng, Heng Guo, Yiyao Zhang
We give an approximate sampler for ferromagnetic Ising models with no field on arbitrary graphs that runs in time , w…
An -time 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 for arbitrary nonnegat…
Approximating spin systems on planar graphs
Heng Guo, Xinyuan Zhang
We show that the hard-core partition function admits a fully polynomial-time randomised approximation scheme (FPRAS) on planar graphs when the activity is a sufficiently small cons…
Fast counting and sampling for ferromagnetic two-spin systems
Weiming Feng, Heng Guo, Yichun Yang
We introduce two new models equivalent to ferromagnetic two-spin systems: a weighted subgraph model and a random cluster type model. Using these new connections, we obtain an effic…
Rapid mixing in positively weighted restricted Boltzmann machines
Weiming Feng, Heng Guo, Minji Yang
We show polylogarithmic mixing time bounds for the alternating-scan sampler for positively weighted restricted Boltzmann machines. This is done via analysing the same chain and the…
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…
Near-linear time samplers for matroid independent sets with applications
Xiaoyu Chen, Heng Guo, Xinyuan Zhang +1
We give a time almost uniform sampler for independent sets of a matroid, whose ground set has elements and is given by an independence oracle. As a consequen…