Heng Guo

collaborators

2 papers

cs.DS2025

Approximate Counting for Spin Systems in Sub-Quadratic Time

Konrad Anand, Weiming Feng, Graham Freifeld +2

We present two randomised approximate counting algorithms with $O (n^{2 - c} / ε^{2})$ running time for some constant $c > 0$ and accuracy $ε$ : (1) for the h…

cs.DS2024

Fast sampling of satisfying assignments from random $k$ -SAT with applications to connectivity

Zongchen Chen, Andreas Galanis, Leslie Ann Goldberg +4

We give a nearly linear-time algorithm to approximately sample satisfying assignments in the random $k$ -SAT model when the density of the formula scales exponentially with $k$ . The…

Approximate Counting for Spin Systems in Sub-Quadratic Time

Fast sampling of satisfying assignments from random k-SAT with applications to connectivity

Fast sampling of satisfying assignments from random $k$ -SAT with applications to connectivity