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

CREATORXiaoyu Chen, Zongchen Chen, Kuikui Liu, Xinyuan Zhang
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE138201
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.02235

Browse the full library · About the Tower of Babel