betaFeedback

WorksComputer Science

Approximating #BIS in exp⁡(O~(n1/3))\exp(\widetilde O(n^{1/3})) Time

Abstract

We give randomized algorithms for approximately counting and nearly uniformly sampling independent sets in arbitrary bipartite graphs (#BIS). At fixed accuracy, both algorithms run in exp⁡(O(n1/3log⁡4/3n))\exp(O(n^{1/3}\log^{4/3}n)) time on nn-vertex graphs. More generally, the same running-time dependence on the number of variables holds for approximate counting and sampling with efficiently evaluable positive log-supermodular weights on Boolean variables. A weighted Sinclair-Jerrum walk on the self-reduction tree reduces these tasks to coarse lower estimates of residual log-partition functions. We obtain these estimates by optimizing a concave relaxation of an exact variational principle on the tree; threshold smoothing certifies that the low-degree search suffices.

Introduction

Given a bipartite graph GG, the problem #BIS asks for the number Z(G)Z(G) of its independent sets. Exact counting is #P-complete even on bipartite graphs [73]. In approximate counting, #BIS represents a broad class of problems equivalent to it under approximation-preserving reductions. Dyer, Goldberg, Greenhill, and Jerrum [25] showed that #BIS is complete for a logically defined class #RHΠ1\Pi_1 under these reductions. Equivalent problems include counting downsets of a partial order and satisfying assignments of conjunctions of implications [25], counting stable matchings [48, 25, 15], and approximating the partition function of the ferromagnetic Ising model with mixed local fields [35]. #BIS is also a benchmark for weighted constraints, spin systems, and list homomorphisms [4, 9, 38, 34].

By the trichotomy of Dyer, Goldberg, and Jerrum [26], every counting constraint satisfaction problem with a fixed finite set of Boolean relations is polynomial-time computable, #BIS-equivalent, or equivalent to counting satisfying assignments of Boolean formulas (#SAT). Yet the approximation complexity of the #BIS-equivalent case remains unresolved: algorithmic techniques have not yielded a fully polynomial randomized approximation scheme (FPRAS), and hardness reductions have not established NP-hardness of approximation [25]. The problems in this equivalence class are conjectured to have intermediate approximation complexity: they have no FPRAS, yet they are strictly easier to approximate than #SAT [25, 36, 13]. Determining the approximation complexity of #BIS, and hence of this entire equivalence class, is a central open problem in the area of approximate counting.

#BIS also fits into the broader framework of log-supermodular weights on Boolean variables: positive weights whose logarithms are supermodular set functions. This is the FKG lattice condition [32], also called multivariate total positivity of order two (MTP2) [58]. The framework includes ferromagnetic Ising models with arbitrary local fields, whose partition functions are #BIS-equivalent [35]; when all fields favor the same spin, they admit an FPRAS [55]. It also allows terms coupling more than two variables. For #BIS, summing out one side gives such a weight on the other, with no more variables than vertices. Log-supermodularity also marks a complexity boundary for Boolean weighted counting CSPs with nonnegative constraints and all unary weights available: apart from a tractable class generated by unary weights and disequality, a non-log-supermodular constraint gives #SAT-equivalence [4 Theorem 10.2]. Whether general log-supermodular counting reduces to #BIS remains open [9 Theorem 6].

Substantial algorithmic progress has been made on restricted graph classes and in favorable parameter regimes. High-temperature algorithms exploit weak long-range dependence through correlation decay or rapid mixing. The hard-core model weights an independent set II by λ∣I∣\lambda^{|I|} for a fugacity λ>0\lambda> 0. On graphs of maximum degree at most a fixed Δ≥3\Delta\ge3, Weitz’s correlation-decay algorithm [Wei06] gives a deterministic fully polynomial-time approximation scheme (FPTAS) whenever λ<λc(Δ)=(Δ−1)Δ−1/(Δ−2)Δ\lambda< \lambda_c(\Delta) = (\Delta- 1)^{\Delta-1}/(\Delta- 2)^\Delta, the uniqueness threshold of the infinite Δ\Delta-regular tree. At λ=1\lambda= 1 this means maximum degree at most five, and Liu and Lu [62] need this bound on one side only. With the same fugacity on both sides, Chen, Liu, and Yin [21] show that λc(Δ)\lambda_c(\Delta) remains the uniqueness threshold when the degree bound Δ\Delta holds on one side only, and they sample rapidly below it. Low-temperature algorithms exploit concentration around structured phases. Algorithmic Pirogov–Sinai theory gives high-fugacity algorithms on lattice regions with suitable boundary conditions [47] and beyond lattices [18]. Polymer methods yield approximation algorithms on bounded-degree bipartite expanders [50] and on bipartite graphs with sufficiently unbalanced degrees or fugacities [22], the latter including λ=1\lambda= 1. On almost every random regular bipartite graph of sufficiently large fixed degree, recent work of Kocurek, Oveis Gharan, and Tjowasi [57], together with [50], covers all fugacities. Graph containers give an FPTAS for #BIS on weakly expanding regular bipartite graphs of large fixed degree, and inverse-polynomial relative approximation in subexponential time on regular bipartite graphs of growing degree [54]; spectral methods give an FPRAS in the dense regular case [10]. These guarantees rely on assumptions that need not hold on arbitrary bipartite graphs.

Recent announcements of subexponential-time algorithms for exactly counting satisfying assignments of fixed-width CNF formulas [72, 20] would, if confirmed, yield 2O(nlog⁡log⁡n/log⁡n)2^{O(n\log\log n/\sqrt{\log n})}-time exact counting algorithms for #BIS on arbitrary nn-vertex bipartite graphs. Before these announcements, the best known approximation algorithm for #BIS was the deterministic approximation algorithm of Goldberg, Lapinskas, and Richerby [39], running in time O(20.2372n)poly⁡(ϵ−1)O(2^{0.2372n})\operatorname{poly}(\epsilon^{-1}) for relative error ϵ\epsilon. The conjectured intermediate approximation complexity of the #BIS-equivalent class motivates the search for algorithms substantially faster than those available for SAT. Against the traditional exponential-time benchmark for SAT, obtaining a subexponential-time approximation algorithm for #BIS has been a prominent open direction in approximate counting (see, e.g., [74, 60]). The question was explicitly posed by Jenssen, Perkins, and Potukuchi [54 Question 1] and reiterated by Carlson, Davies, Kolla, and Potukuchi [10]. If confirmed, the announced algorithms would answer the question as stated, while also changing the SAT benchmark. The underlying algorithmic goal remains to exploit the special structure of #BIS to obtain algorithms substantially faster than those available for SAT. Against the announced SAT bounds, a natural quantitative target is a fixed-power saving in the exponent: does #BIS admit a 2O(nc)2^{O(n^c)}-time approximation algorithm at fixed accuracy for some fixed 0<c<10<c<1?

Results

We resolve this question by giving randomized algorithms for approximately counting and nearly uniformly sampling independent sets in arbitrary bipartite graphs. At fixed accuracy, both algorithms run in exp⁡(O(n1/3log⁡4/3n))\exp(O(n^{1/3}\log^{4/3} n)) time on nn-vertex graphs. We state the precise bounds in the exact real-arithmetic model of § 5; implementations using bit operations and fair random bits have the same exponential factors (Theorem A.1).

Write I(G)\mathcal{I}(G) for the independent sets of GG, Z(G)=∣I(G)∣Z(G)=|\mathcal{I}(G)|, and UGU_G for the uniform law on I(G)\mathcal{I}(G).

Theorem 1.1 (Bipartite independent sets). There are randomized algorithms with the following guarantees for every bipartite graph GG with n≥2n\ge2 vertices.

  1. For every real 0<η≤1/20<\eta\le1/2, the sampling algorithm returns an independent set of GG whose law is within total variation distance η\eta of UGU_G. Its running time is at most

exp⁡(O(n1/3log⁡4/3n))poly⁡(n,log⁡(1/η)).\exp\left(O\left(n^{1/3}\log^{4/3} n\right)\right)\operatorname{poly}(n,\log(1/\eta)).
  1. For all reals ϵ,δ∈(0,1/2]\epsilon,\delta\in(0,1/2], the counting algorithm returns an estimate Z^\widehat{Z} satisfying

Pr⁡[∣Z^Z(G)−1∣≤ϵ]≥1−δ.\Pr\left[\left|\frac{\widehat{Z}}{Z(G)}-1\right|\le\epsilon\right]\ge1-\delta.

Its running time is at most

exp⁡(O(n1/3log⁡4/3n))poly⁡(n,ϵ−1,log⁡(1/δ)).\exp\left(O\left(n^{1/3}\log^{4/3} n\right)\right)\operatorname{poly}(n,\epsilon^{-1},\log(1/\delta)).

Both bounds hold on every execution in the exact real-arithmetic model.

The constants are absolute. For rational accuracy and failure-probability parameters, Theorem A.1 gives a bit implementation with polynomial overhead in their encoding lengths.

Log-supermodular weights. The algorithms follow from a general result for log-supermodular weights on Boolean variables. A positive weight W:{0,1}d→Q>0W : \{0,1\}^{d} \to\mathbb{Q}_{>0} is log-supermodular if

W(x∧y)W(x∨y)≥W(x)W(y)(x,y∈{0,1}d),(1)W(x \wedge y) W(x \vee y) \ge W(x) W(y) \qquad(x,y \in\{0,1\}^{d}), \tag*{(1)}

where ∧\wedge and ∨\vee are the coordinatewise minimum and maximum.

The algorithms receive the dimension d≥2d \ge2 and use the following representation of WW.

  • (Exact evaluation) The weight is given by an exact evaluator using at most TWT_W operations per value; in the bit implementation, TWT_W denotes the bit cost of returning an exact rational value.

  • (Value length) The algorithms receive a bound B≥1B \ge1 on the bit length of every value of WW, where the bit length of a rational is the larger of those of its numerator and denominator.

Write ZW=∑xW(x)Z_W = \sum_x W(x) for the partition function and μW=W/ZW\mu_W = W/Z_W for the target law.

Theorem 1.2 (Log-supermodular weights). For every log-supermodular weight WW given in this representation, there are randomized algorithms with the following guarantees.

(i) For every real 0<η≤1/20 < \eta\le1/2, the sampling algorithm returns a configuration whose law is within total variation distance η\eta of μW\mu_W. Its running time is at most

exp⁡(O(min⁡{d,d1/3log⁡2/3dlog⁡2/3(d+B)}))poly⁡(d,B,TW,log⁡(1/η)).\exp\left(O\left(\min\left\{d,d^{1/3}\log^{2/3}d\log^{2/3}(d+B)\right\}\right)\right)\operatorname{poly}(d,B,T_W,\log(1/\eta)).

(ii) For all reals ϵ,δ∈(0,1/2]\epsilon,\delta\in(0,1/2], the counting algorithm returns an estimate Z^\widehat{Z} satisfying

Pr⁡[∣Z^ZW−1∣≤ϵ]≥1−δ.\Pr\left[\left|\frac{\widehat{Z}}{Z_W}-1\right|\le\epsilon\right]\ge1-\delta.

Its running time is at most

exp⁡(O(min⁡{d,d1/3log⁡2/3dlog⁡2/3(d+B)}))poly⁡(d,B,TW,ϵ−1,log⁡(1/δ)).\exp\left(O\left(\min\left\{d,d^{1/3}\log^{2/3}d\log^{2/3}(d+B)\right\}\right)\right)\operatorname{poly}(d,B,T_W,\epsilon^{-1},\log(1/\delta)).

Both bounds hold on every execution in the exact real-arithmetic model.

When BB and TWT_W are polynomial in dd, both algorithms run in exp⁡(O(d1/3log⁡4/3d))\exp(O(d^{1/3}\log^{4/3}d)) time at fixed accuracy. The algorithms access WW only through its evaluator; no factorization into local interactions or correlation-decay assumption is required.

To apply Theorem 1.2 to #BIS, let G=(L,R,E)G=(L,R,E) be a bipartite graph and write N(S)N(S) for the neighborhood of a vertex set SS and N(r)=N({r})N(r)=N(\{r\}). Summing out RR gives the positive weight

W(S)=2∣R∖N(S)∣(S⊆L),(2)W(S)=2^{|R\setminus N(S)|} \qquad(S\subseteq L), \tag*{(2)}

since SS can be completed to an independent set by adjoining any subset of R∖N(S)R\setminus N(S).

Proof of Theorem 1.1 from Theorem 1.2. If ∣L∣≤1|L|\le1, the at most two choices of S⊆LS\subseteq L, together with (1.2), give exact counting and sampling algorithms in polynomial time. Otherwise set d=∣L∣≥2d=|L|\ge2. For S,S′⊆LS,S'\subseteq L, we have N(S∪S′)=N(S)∪N(S′)N(S\cup S')=N(S)\cup N(S') and N(S∩S′)⊆N(S)∩N(S′)N(S\cap S')\subseteq N(S)\cap N(S'), so

∣N(S∪S′)∣+∣N(S∩S′)∣≤∣N(S)∣+∣N(S′)∣.|N(S\cup S')|+|N(S\cap S')|\le|N(S)|+|N(S')|.

Thus the coverage function S↦∣N(S)∣S\mapsto|N(S)| is submodular, so log⁡W\log W is supermodular and WW satisfies (1.1). The values are integers at most 2n2^n, so we may take B=n+1B=n+1 and TW=poly⁡(n)T_W=\operatorname{poly}(n). Since ZW=Z(G)Z_W=Z(G), the counter of Theorem 1.2 counts independent sets.

References

  1. [1][ALOG20] Nima Anari, Kuikui Liu, and Shayan Oveis Gharan. Spectral independence in high-dimensional expanders and applications to the hardcore model. In FOCS, pages 1319–1330, 2020. doi:10.1109/FOCS46700.2020.00125.arxiv.org/abs/2001.00303
  2. [2]Francis Bach. Learning with submodular functions: A convex optimization perspective. Foundations and Trends in Machine Learning, 6(2–3):145–373, 2013. Numbering follows arXiv:1111.6453v2. URL: https://arxiv.org/abs/1111.6453.
  3. [3]Antonio Blanca, Sarah Cannon, and Will Perkins. Fast and perfect sampling of subgraphs and polymer systems. ACM Transactions on Algorithms, 20(1), 2024. Article 5. doi:10.1145/3632294.DOI
  4. [4]Andrei A. Bulatov, Martin Dyer, Leslie Ann Goldberg, Mark Jerrum, and Colin McQuillan. The expressibility of functions on the Boolean domain, with applications to counting CSPs. Journal of the ACM, 60(5):32:1–32:36, 2013. doi:10.1145/2528401.DOI
  5. [5]Alexander Barvinok and Alex Samorodnitsky. Random weighting, asymptotic counting, and inverse isoperimetry. Israel Journal of Mathematics, 158:159–191, 2007. arXiv:math/0302177. URL: https://arxiv.org/abs/math/0302177.
  6. [6]Richard P. Brent and Paul Zimmermann. Modern Computer Arithmetic, volume 18 of Cambridge Monographs on Applied and Computational Mathematics. Cambridge University Press, Cambridge, 2010. doi:10.1017/CBO9780511921698.DOI
  7. [7]Xiaoyu Chen, Zongchen Chen, Yitong Yin, and Xinyuan Zhang. Rapid mixing at the uniqueness threshold. In STOC, pages 879–890, 2025. Current full version: arXiv:2411.03413. URL: https://arxiv.org/abs/2411.03413, doi:10.1145/3717823.3718260.
  8. [8]Radu Curticapean, Holger Dell, Fedor Fomin, Leslie Ann Goldberg, and John Lapinskas. A fixed-parameter perspective on #BIS. Algorithmica, 81:3844–3864, 2019. Preliminary version in IPEC 2017. doi:10.1007/s00453-019-00606-4.
  9. [9]Xi Chen, Martin Dyer, Leslie Ann Goldberg, Mark Jerrum, Pinyan Lu, Colin McQuillan, and David Richerby. The complexity of approximating conservative counting CSPs. Journal of Computer and System Sciences, 81(1):311–329, 2015. doi:10.1016/j.jcss.2014.06.006.DOI
  10. [10]Charlie Carlson, Ewan Davies, Alexandra Kolla, and Aditya Potukuchi. A spectral approach to approximately counting independent sets in dense bipartite graphs. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024), volume 297 of LIPIcs, pages 35:1–35:18, 2024. doi:10.4230/LIPIcs.ICALP.2024.35.DOI
  11. [11]Xiaoyu Chen and Weiming Feng. Rapid mixing via coupling independence for spin systems with unbounded degree. In APPROX/RANDOM, volume 353 of LIPIcs, pages 68:1–68:17, 2025. doi:10.4230/LIPIcs.APPROX/RANDOM.2025.68.
  12. [12]Xiaoyu Chen, Weiming Feng, Yitong Yin, and Xinyuan Zhang. Rapid mixing of Glauber dynamics via spectral independence for all degrees. In FOCS, pages 137–148, 2021. doi:10.1109/FOCS52979.2021.00022.DOI
  13. [13]Jin-Yi Cai, Andreas Galanis, Leslie Ann Goldberg, Heng Guo, Mark Jerrum, Daniel Štefankovič, and Eric Vigoda. #BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region. Journal of Computer and System Sciences, 82(5):690–711, 2016. doi:10.1016/j.jcss.2015.11.009.DOI
  14. [14][CGG+21] Zongchen Chen, Andreas Galanis, Leslie A. Goldberg, Will Perkins, James Stewart, and Eric Vigoda. Fast algorithms at low temperatures via Markov chains. Random Structures & Algorithms, 58(2):294–321, 2021. doi:10.1002/rsa.20968.DOI
  15. [15][CGM12] Prasad Chebolu, Leslie Ann Goldberg, and Russell Martin. The complexity of approximately counting stable matchings. Theoretical Computer Science, 437:35–68, 2012. URL: https://arxiv.org/abs/1004.1836, doi:10.1016/j.tcs.2012.02.029.
  16. [16][CGMW26] Katie Clinch, Serge Gaspers, Simon Mackenzie, and Qi Wang. Faster exponential-time approximate counting via bounded self-reductions. In 34th Annual European Symposium on Algorithms (ESA 2026), volume 388 of LIPIcs, pages 104:1–104:14, 2026. doi:10.4230/LIPIcs.ESA.2026.104.DOI
  17. [17][CGŠV22] Zongchen Chen, Andreas Galanis, Daniel Štefankovič, and Eric Vigoda. Sampling colorings and independent sets of random regular bipartite graphs in the non-uniqueness region. In SODA 2022, pages 2198–2207, 2022. doi:10.1137/1.9781611977073.87.DOI
  18. [18][CHP26] Sarah Cannon, Tyler Helmuth, and Will Perkins. Pirogov–Sinai theory for the hard-core model beyond lattices. Communications in Mathematical Physics, 407:129, 2026. arXiv:2411.07809. URL: https://arxiv.org/abs/2411.07809.
  19. [19][CJ25] Zongchen Chen and Tianhui Jiang. Improved mixing of critical hardcore model. In APPROX/RANDOM, volume 353 of LIPIcs, pages 51:1–51:22, 2025. doi:10.4230/LIPIcs.APPROX/RANDOM.2025.51.DOI
  20. [20][Cla26] Claude (Anthropic). A 2^{o(n)} time algorithm for 3-SAT, 2026. Research manuscript. URL: https://github.com/anthropics/formal-math/blob/main/eth/README.md.
  21. [21][CLY23] Xiaoyu Chen, Jingcheng Liu, and Yitong Yin. Uniqueness and rapid mixing in the bipartite hardcore model (extended abstract). In FOCS, pages 1991–2005, 2023. Full version: arXiv:2305.00186. URL: https://arxiv.org/abs/2305.00186, doi:10.1109/FOCS57990.2023.00121.
  22. [22][CP20] Sarah Cannon and Will Perkins. Counting independent sets in unbalanced bipartite graphs. In SODA 2020, pages 1456–1466, 2020. doi:10.1137/1.9781611975994.88.DOI
  23. [23][CT06] Thomas M. Cover and Joy A. Thomas. Elements of Information Theory. Wiley-Interscience, Hoboken, NJ, second edition, 2006. doi:10.1002/047174788X.
  24. [24][DFJ02] Martin Dyer, Alan Frieze, and Mark Jerrum. On counting independent sets in sparse graphs. SIAM Journal on Computing, 31(5):1527–1541, 2002. doi:10.1137/S0097539701383844.DOI
  25. [25][DGGJ04] Martin Dyer, Leslie Ann Goldberg, Catherine Greenhill, and Mark Jerrum. The relative complexity of approximate counting problems. Algorithmica, 38(3):471–500, 2004. doi:10.1007/s00453-003-1073-y.DOI
  26. [26][DGJ10] Martin Dyer, Leslie Ann Goldberg, and Mark Jerrum. An approximation trichotomy for Boolean #CSP. Journal of Computer and System Sciences, 76(3–4):267–277, 2010. doi:10.1016/j.jcss.2009.08.003.DOI
  27. [27]Josip Djolonga and Andreas Krause. From MAP to marginals: Variational inference in Bayesian submodular models. In Advances in Neural Information Processing Systems, volume 27, 2014. URL: https://proceedings.neurips.cc/paper_files/paper/2014/file/efe0df3ea4a53a04614ad79e7a8a57de-Paper.pdf.
  28. [28]Josip Djolonga and Andreas Krause. Scalable variational inference in log-supermodular models. In ICML, volume 37 of PMLR, pages 1804–1813, 2015. URL: https://proceedings.mlr.press/v37/djolonga15.html.
  29. [29]B. Efron and C. Stein. The jackknife estimate of variance. The Annals of Statistics, 9(3):586–596, 1981. doi:10.1214/aos/1176345462.DOI
  30. [30]Robert G. Edwards and Alan D. Sokal. Generalization of the Fortuin–Kasteleyn–Swendsen–Wang representation and Monte Carlo algorithm. Physical Review D, 38(6):2009–2012, 1988. doi:10.1103/PhysRevD.38.2009.DOI
  31. [31]Tobias Friedrich, Andreas Göbel, Martin S. Krejca, and Marcus Pappik. Polymer dynamics via cliques: New conditions for approximations. Theoretical Computer Science, 942:230–252, 2023. URL: https://arxiv.org/abs/2007.08293.
  32. [32]C. M. Fortuin, P. W. Kasteleyn, and J. Ginibre. Correlation inequalities on some partially ordered sets. Communications in Mathematical Physics, 22:89–103, 1971. doi:10.1007/BF01651330.DOI
  33. [33]Weiming Feng and Minji Yang. Rapid mixing of Glauber dynamics for monotone systems via entropic independence. In SODA, pages 4894–4929, 2026. doi:10.1137/1.9781611978971.177.DOI
  34. [34]Andreas Galanis, Leslie Ann Goldberg, and Mark Jerrum. A complexity trichotomy for approximately counting list H-colorings. ACM Transactions on Computation Theory, 9(2):9:1–9:22, 2017. doi:10.1145/3037381.DOI
  35. [35]Leslie Ann Goldberg and Mark Jerrum. The complexity of ferromagnetic Ising with local fields. Combinatorics, Probability and Computing, 16(1):43–61, 2007. doi:10.1017/S096354830600767X.DOI
  36. [36]Leslie Ann Goldberg and Mark Jerrum. Approximating the partition function of the ferromagnetic Potts model. Journal of the ACM, 59(5):25:1–25:31, 2012. doi:10.1145/2371656.2371660.DOI
  37. [37]Leslie Ann Goldberg and Mark Jerrum. A counterexample to rapid mixing of the Ge–Štefankovič process. Electronic Communications in Probability, 17(5):1–6, 2012. doi:10.1214/ECP.v17-1712.DOI
  38. [38]Leslie Ann Goldberg and Mark Jerrum. A complexity classification of spin systems with an external field. Proceedings of the National Academy of Sciences, 112(43):13161–13166, 2015. doi:10.1073/pnas.1505664112.DOI
  39. [39]Leslie Ann Goldberg, John Lapinskas, and David Richerby. Faster exponential-time algorithms for approximately counting independent sets. Theoretical Computer Science, 892:48–84, 2021. doi:10.1016/j.tcs.2021.09.009.DOI
  40. [40]Geoffrey R. Grimmett. The Random-Cluster Model, volume 333 of Grundlehren der mathematischen Wissenschaften. Springer, Berlin, Heidelberg, 2006. doi:10.1007/978-3-540-32891-9.
  41. [41]Qi Ge and Daniel Štefankovič. A graph polynomial for independent sets of bipartite graphs. Combinatorics, Probability and Computing, 21(5):695–714, 2012. Preliminary version in FSTTCS 2010. doi:10.1017/S0963548312000296.
  42. [42]Tamir Hazan and Tommi Jaakkola. On the partition function and random maximum a-posteriori perturbations. In Proceedings of the 29th International Conference on Machine Learning (ICML), Edinburgh, 2012. arXiv:1206.6410. URL: https://arxiv.org/abs/1206.6410.
  43. [43]Mark Huber and Jenny Law. Fast approximation of the permanent for very dense problems. In Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2008.
  44. [44]Tamir Hazan, Subhransu Maji, and Tommi Jaakkola. On sampling from the Gibbs distribution with random maximum a-posteriori perturbations. In Advances in Neural Information Processing Systems 26 (NIPS), 2013. arXiv:1309.7598. URL: https://arxiv.org/abs/1309.7598.
  45. [45]Wassily Hoeffding. A class of statistics with asymptotically normal distribution. The Annals of Mathematical Statistics, 19(3):293–325, 1948. doi:10.1214/aoms/1177730196.DOI
  46. [46]Wassily Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58(301):13–30, 1963. doi:10.1080/01621459.1963.10500830.DOI
  47. [47]Tyler Helmuth, Will Perkins, and Guus Regts. Algorithmic Pirogov–Sinai theory. Probability Theory and Related Fields, 176:851–895, 2020. doi:10.1007/s00440-019-00928-y.DOI
  48. [48]Robert W. Irving and Paul Leather. The complexity of counting stable marriages. SIAM Journal on Computing, 15(3):655–667, 1986. doi:10.1137/0215048.DOI
  49. [49]Vishesh Jain, Frederic Koehler, and Elchanan Mossel. The mean-field approximation: Information inequalities, algorithms, and complexity. In COLT, volume 75 of PMLR, pages 1326–1347, 2018. URL: https://proceedings.mlr.press/v75/jain18b.html.arxiv.org/abs/1802.06126
  50. [50]Matthew Jenssen, Peter Keevash, and Will Perkins. Algorithms for #BIS-hard problems on expander graphs. SIAM Journal on Computing, 49(4):681–710, 2020. doi:10.1137/19M1286669.DOI
  51. [51]Vishesh Jain, Frederic Koehler, and Andrej Risteski. Mean-field approximation, convex hierarchies, and the optimality of correlation rounding: A unified perspective. In STOC, pages 1226–1236, 2019. doi:10.1145/3313276.3316299.DOI
  52. [52]Zhe Ju, Jingcheng Liu, and Yitong Yin. Fine-grained complexity across the computational phase transition, 2026. Manuscript.arxiv.org/abs/2611.02702
  53. [53]Matthew Jenssen, Alexandru Malekshahian, and Jinyoung Park. A refined graph container lemma and applications to the hard-core model on bipartite expanders. Random Structures & Algorithms, 68(1):e70041, 2026. doi:10.1002/rsa.70041.DOI
  54. [54]Matthew Jenssen, Will Perkins, and Aditya Potukuchi. Approximately counting independent sets in bipartite graphs via graph containers. Random Structures & Algorithms, 63(1):215–241, 2023. doi:10.1002/rsa.21145.
  55. [55]Mark Jerrum and Alistair Sinclair. Polynomial-time approximation algorithms for the Ising model. SIAM Journal on Computing, 22(5):1087–1116, 1993. doi:10.1137/0222066.
  56. [56]Mark R. Jerrum, Leslie G. Valiant, and Vijay V. Vazirani. Random generation of combinatorial structures from a uniform distribution. Theoretical Computer Science, 43:169–188, 1986. doi:10.1016/0304-3975(86)90174-X.
  57. [57]Nicholas Kocurek, Shayan Oveis Gharan, and Dante Tjowasi. Sampling from the hardcore model on random regular bipartite graphs above the uniqueness threshold, 2026. Preprint, arXiv:2604.21847. URL: https://arxiv.org/abs/2604.21847.
  58. [58]Samuel Karlin and Yosef Rinott. Classes of orderings of measures and related correlation inequalities. I. Multivariate totally positive distributions. Journal of Multivariate Analysis, 10(4):467–498, 1980. doi:10.1016/0047-259X(80)90065-2.
  59. [59]Donald E. Knuth and Andrew C. Yao. The complexity of nonuniform random number generation. In Joseph F. Traub, editor, Algorithms and Complexity: New Directions and Recent Results, pages 357–428. Academic Press, New York, 1976.
  60. [60]Kuikui Liu. 6.S891 lecture 11: The polymer method and the cluster expansion, October 2023. Lecture notes, October 17, 2023; see Question 2, page 9. URL: https://kuikuiliu.github.io/files/au2023/6S891-lec11.pdf.
  61. [61]Elliott H. Lieb and Michael Loss. Analysis, volume 14 of Graduate Studies in Mathematics. American Mathematical Society, Providence, RI, second edition, 2001. doi:10.1090/gsm/014.DOI
  62. [62]Jingcheng Liu and Pinyan Lu. FPTAS for #BIS with degree bounds on one side. In Proceedings of the 47th Annual ACM Symposium on Theory of Computing (STOC 2015), pages 549–556, 2015. doi:10.1145/2746539.2746598.
  63. [63]Chao Liao, Jiabao Lin, Pinyan Lu, and Zhenyu Mao. An FPTAS for the hardcore model on random regular bipartite graphs. Theoretical Computer Science, 929:174–190, 2022. doi:10.1016/j.tcs.2022.07.001.
  64. [64]Nathan Linial, Yishay Mansour, and Noam Nisan. Constant depth circuits, Fourier transform, and learnability. Journal of the ACM, 40(3):607–620, 1993. doi:10.1145/174130.174138.
  65. [65]László Lovász. Submodular functions and convexity. In Achim Bachem, Martin Grötschel, and Bernhard Korte, editors, Mathematical Programming: The State of the Art (Bonn, 1982), pages 235–257. Springer, Berlin, 1983. doi:10.1007/978-3-642-68874-4_10.DOI
  66. [66]Ankur Moitra. Approximate counting, the Lovász local lemma, and inference in graphical models. Journal of the ACM, 66(2):1–25, 2019. Preliminary version in Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC), 2017, pages 356–369. doi:10.1145/3268930.DOI
  67. [67]Elchanan Mossel, Dror Weitz, and Nicholas Wormald. On the hardness of sampling independent sets beyond the tree threshold. Probability Theory and Related Fields, 143(3–4):401–439, 2009. doi:10.1007/s00440-007-0131-9.DOI
  68. [68]Tianshun Miao and Yitong Yin. Sampling matchings in near-linear time, 2026. URL: https://arxiv.org/abs/2609.21936, arXiv:2609.21936, doi:10.48550/arXiv.2609.21936.
  69. [69]Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro. Robust stochastic approximation approach to stochastic programming. SIAM Journal on Optimization, 19(4):1574–1609, 2009. doi:10.1137/070704277.DOI
  70. [70]Ijay Narang, Will Perkins, Yuzhou Wang, and Timothy L. H. Wee. Computational thresholds for balanced and fixed-slice independent sets in bipartite graphs, 2026. Preprint, arXiv:2608.02503. URL: https://arxiv.org/abs/2608.02503.
  71. [71]Ryan O’Donnell. Analysis of Boolean Functions. Cambridge University Press, New York, 2014. Numbering follows arXiv:2105.10386. doi:10.1017/CBO9781139814782.DOI
  72. [72]OpenAI. The Exponential Time Hypothesis is false, 2026. Research manuscript, revised October 25, 2026. URL: https://github.com/openai/math/blob/main/preprints/The-Exponential-Time-Hypothesis-is-False-October-25-2026/build/main_full_version.tex.
  73. [73]J. Scott Provan and Michael O. Ball. The complexity of counting cuts and of computing the probability that a graph is connected. SIAM Journal on Computing, 12(4):777–788, 1983. doi:10.1137/0212053.DOI
  74. [74]Will Perkins. Counting and sampling algorithms at low temperature. Talk at the STOC workshop “New Frontiers in Approximate Counting”, 2020. Slides; see slide 29, “Open Questions”. URL: https://homepages.inf.ed.ac.uk/hguo/slides/STOCworkshop-Will.pdf.
  75. [75]Andrej Risteski. How to calculate partition functions using convex programming hierarchies: Provable bounds for variational methods. In COLT, volume 49 of PMLR, pages 1402–1416, 2016. URL: https://proceedings.mlr.press/v49/risteski16.html.arxiv.org/abs/1607.03183
  76. [76]Murray Rosenblatt. Remarks on a multivariate transformation. The Annals of Mathematical Statistics, 23(3):470–472, 1952. doi:10.1214/aoms/1177729394.DOI
  77. [77]Nicholas Ruozzi. The Bethe partition function of log-supermodular graphical models. In Advances in Neural Information Processing Systems, volume 25, 2012. URL: https://proceedings.neurips.cc/paper_files/paper/2012/file/03afdbd66e7929b125f8597834fa83a4-Paper.pdf.arxiv.org/abs/1202.6035

Paper details

vlnc:W_4rkc8xj4
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 10

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents