Approximating #BIS in $\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(n^{1/3}\log^{4/3}n))$ time on $n$-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.

The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.

More in Data Structures & Algorithms

• arXiv preprint · 4 November 2026

  Noncrossing is All You Need: Beyond Identical Delay Functions in Online Matching with Delays on General Metrics

  Yossi Azar, Junhao Gan, Shahar Lewkowicz and 2 others
• arXiv preprint · 5 November 2026

  Quadratic-Time Barriers from Self-Referential SAT

  Guangyan Zhou
• arXiv preprint · 4 November 2026

  Sublinear Metric Distortion for Matching

  Moses Charikar, Alireza Haqi, Jabari Hastings and 2 others
• arXiv preprint · 5 November 2026

  Exact $\ell_p$-CVP via Euclidean SVP in Polynomial Space

  Jiseung Kim, Minkyu Kim and Hyung Tae Lee
• arXiv preprint · 4 November 2026

  Near linear mixing of random-cluster Glauber dynamics on random regular graphs

  Zhangsong Li

All new papers in Data Structures & Algorithms