Reproduce “Approximating #BIS in $\exp(\widetilde O(n^{1/3}))$ Time” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Jingcheng Liu, Yitong Yin
The authors give randomized algorithms for approximately counting and nearly uniformly sampling independent sets in every bipartite graph. They estimate coarse lower bounds on residual partition functions, then use them in a weighted walk on a self-reduction tree. At fixed accuracy, both run in exp(O(n^{1/3} log^{4/3} n)) time, without structural assumptions; this is a theoretical guarantee, not evidence of practical performance.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.