2026-08-13T05:31:33Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20154 2024-07-02T07:52:48Z ddc:004 open_access

Approximate Counting for Spin Systems in Sub-Quadratic Time Anand, Konrad Feng, Weiming Freifeld, Graham Guo, Heng Wang, Jiaheng Randomised algorithm Approximate counting Spin system Sub-quadratic algorithm We present two randomised approximate counting algorithms with Õ(n^{2-c}/ε²) running time for some constant c > 0 and accuracy ε: 1) for the hard-core model with fugacity λ on graphs with maximum degree Δ when λ = O(Δ^{-1.5-c₁}) where c₁ = c/(2-2c); 2) for spin systems with strong spatial mixing (SSM) on planar graphs with quadratic growth, such as ℤ². For the hard-core model, Weitz’s algorithm (STOC, 2006) achieves sub-quadratic running time when correlation decays faster than the neighbourhood growth, namely when λ = o(Δ^{-2}). Our first algorithm does not require this property and extends the range where sub-quadratic algorithms exist. Our second algorithm appears to be the first to achieve sub-quadratic running time up to the SSM threshold, albeit on a restricted family of graphs. It also extends to (not necessarily planar) graphs with polynomial growth, such as ℤ^d, but with a running time of the form Õ(n²ε^{-2}/2^{c(log n)^{1/d}}) where d is the exponent of the polynomial growth and c > 0 is some constant. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Konrad Anand and Weiming Feng and Graham Freifeld and Heng Guo and Jiaheng Wang 2024 Is Part Of LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2024.11 urn:nbn:de:0030-drops-201543 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.11 eng https://creativecommons.org/licenses/by/4.0/legalcode