Subquadratic Counting via Perfect Marginal Sampling
Xiaoyu Chen, Zongchen Chen, Kuikui Liu, Xinyuan Zhang · 2026
Read Subquadratic Counting via Perfect Marginal Sampling by Xiaoyu Chen, Zongchen Chen, Kuikui Liu, Xinyuan Zhang (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-02235.txt.
Description
Chen and colleagues break the quadratic time barrier for approximate counting in spin systems. Standard counting to sampling reductions run in quadratic time. Their new algorithms run subquadratically across many settings, including the hardcore model of weighted independent sets and the Ising model. The key link is perfect marginal sampling. For two spin systems, a perfect marginal sampler directly yields a fast counting algorithm. For general spin systems, adapted samplers yield low variance estimators in sublinear time.
Catalog record
| CREATOR | Xiaoyu Chen, Zongchen Chen, Kuikui Liu, Xinyuan Zhang |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 138201 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.02235