We study approximately uniform sampling of satisfying assignments from random $k$-SAT formulas. For every sufficiently large $k$ and density $0<\alpha \le 2^k/k^{16}$, we prove that, with high probability over the formula, there is a sampler whose output distribution is within total variation distance $\varepsilon$ of...
A framework for deterministic approximate counting of multi-spin systems beyond bounded-degree graphs and extends the framework to proper colorings of sparse Erd\H{o}s-R\'{e}nyi random graphs using recursion on permissive blocks.
We develop a framework for deterministic approximate counting of multi-spin systems beyond bounded-degree graphs. The algorithm recursively constructs rational polytopes containing the true marginal vectors and uses linear-fractional programming to obtain certified bounds on marginal ratios. For positive interactions o...
We design randomized approximation schemes for the partition function of antiferromagnetic Ising models with uniform external field on random regular bipartite graphs. Our algorithm generalizes the approach of Kocurek, Oveis Gharan and Tjowasi (arXiv, 2026) for hard-core models on the same random graph model beyond the...
Zhi-Dan Li, Kuan Yang· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
