2 citations · 2 across the 4 of their papers we have counts for
7 papers
Approximate counting of vertices of 0/1 polytopes: a stronger hardness result
Heng Guo, Mark Jerrum
We show that approximately counting the vertices of a bounded 0/1 polytope, presented as a system of rational linear inequalities, is, informally speaking, NP-hard. In particular,…
Approximating two-terminal network reliability
Weiming Feng, Yucheng Fu, Heng Guo
We present a fully polynomial-time randomised approximation scheme (FPRAS) for the two-terminal reliability problem on general graphs, both directed and undirected. We also show th…
Linear time approximation of the TV distance between product distributions
Konrad Anand, Alistair Benford, Heng Guo
We present a linear time approximation algorithm of the total variation distance between two product distributions. The main algorithm was found using ChatGPT 5.6 Sol Ultra.
Sink-free orientations: a local sampler with applications
Konrad Anand, Graham Freifeld, Heng Guo +2
For sink-free orientations in graphs of minimum degree at least , we show that there is a deterministic approximate counting algorithm that runs in time $O((n^{73}/\varepsilon^{…
Rapid mixing of the flip chain over non-crossing spanning trees
Konrad Anand, Weiming Feng, Graham Freifeld +3
We show that the flip chain for non-crossing spanning trees of points in convex position mixes in time . We use connections between Fuss-Catalan structures to c…
An FPRAS for two terminal reliability in directed acyclic graphs
Weiming Feng, Heng Guo
We give a fully polynomial-time randomized approximation scheme (FPRAS) for two terminal reliability in directed acyclic graphs (DAGs). In contrast, we also show the complementing…
A simple polynomial-time approximation algorithm for the total variation distance between two product distributions
Weiming Feng, Heng Guo, Mark Jerrum +1
We give a simple polynomial-time approximation algorithm for the total variation distance between two product distributions.