Approximate counting for spin systems in sub-quadratic time

Konrad Anand; Weiming Feng; Graham Freifeld; Heng Guo; Jiaheng Wang

doi:10.48550/arXiv.2306.14867

Approximate counting for spin systems in sub-quadratic time

Konrad Anand, Weiming Feng, Graham Freifeld, Heng Guo, Jiaheng Wang

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract / Description of output

We present two randomised approximate counting algorithms with O˜(n2−c/ε2) 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−c1) where c1=c/(2−2c);
(2) for spin systems with strong spatial mixing (SSM) on planar graphs with quadratic growth, such as Z2.
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 Zd, but with a running time of the form O˜(n2ε−2/2c(logn)1/d) where d is the exponent of the polynomial growth and c>0 is some constant.

Original language	English
Title of host publication	51st International Colloquium on Automata, Languages, and Programming
Editors	Karl Bringmann, Martin Grohe, Gabriele Puppis, Ola Svensson
Publisher	Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Pages	1-20
Number of pages	20
ISBN (Electronic)	9783959773225
DOIs	https://doi.org/10.48550/arXiv.2306.14867 https://doi.org/10.4230/LIPIcs.ICALP.2024.11
Publication status	Published - 2 Jul 2024
Event	51st EATCS International Colloquium on Automata, Languages and Programming - Tallinn University, Tallinn, Estonia Duration: 8 Jul 2024 → 12 Jul 2024 https://compose.ioc.ee/icalp2024/

Publication series

Name	Leibniz International Proceedings in Informatics
Publisher	Schloss Dagstuhl – Leibniz-Zentrum für Informatik
ISSN (Electronic)	1868-8969

Conference

Conference	51st EATCS International Colloquium on Automata, Languages and Programming
Abbreviated title	ICALP 2024
Country/Territory	Estonia
City	Tallinn
Period	8/07/24 → 12/07/24
Internet address	https://compose.ioc.ee/icalp2024/

Keywords / Materials (for Non-textual outputs)

randomised algorithm
approximate counting
spin system
sub-quadratic algorithm

Access to Document

AnandEtalICALP2024ApproximateCountingforSpinSystemsFinal published version, 914 KBLicence: Creative Commons: Attribution (CC-BY)

NACS - New Approaches to Counting and Sampling
Guo, H.
European Commission
1/01/21 → 30/06/26
Project: Research

Cite this

Anand, K., Feng, W., Freifeld, G., Guo, H., & Wang, J. (2024). Approximate counting for spin systems in sub-quadratic time. In K. Bringmann, M. Grohe, G. Puppis, & O. Svensson (Eds.), 51st International Colloquium on Automata, Languages, and Programming (pp. 1-20). Article 11 (Leibniz International Proceedings in Informatics). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.48550/arXiv.2306.14867, https://doi.org/10.4230/LIPIcs.ICALP.2024.11

Anand, Konrad ; Feng, Weiming ; Freifeld, Graham et al. / Approximate counting for spin systems in sub-quadratic time. 51st International Colloquium on Automata, Languages, and Programming. editor / Karl Bringmann ; Martin Grohe ; Gabriele Puppis ; Ola Svensson. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. pp. 1-20 (Leibniz International Proceedings in Informatics).

@inproceedings{c24338dd7ac340b284adeca36f3ab27f,

title = "Approximate counting for spin systems in sub-quadratic time",

abstract = "We present two randomised approximate counting algorithms with O˜(n2−c/ε2) 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−c1) where c1=c/(2−2c);(2) for spin systems with strong spatial mixing (SSM) on planar graphs with quadratic growth, such as Z2.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 Zd, but with a running time of the form O˜(n2ε−2/2c(logn)1/d) where d is the exponent of the polynomial growth and c>0 is some constant.",

keywords = "randomised algorithm, approximate counting, spin system, sub-quadratic algorithm",

author = "Konrad Anand and Weiming Feng and Graham Freifeld and Heng Guo and Jiaheng Wang",

year = "2024",

month = jul,

day = "2",

doi = "10.48550/arXiv.2306.14867",

language = "English",

series = "Leibniz International Proceedings in Informatics",

publisher = "Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik",

pages = "1--20",

editor = "Karl Bringmann and Martin Grohe and Gabriele Puppis and Ola Svensson",

booktitle = "51st International Colloquium on Automata, Languages, and Programming",

note = "51st EATCS International Colloquium on Automata, Languages and Programming, ICALP 2024 ; Conference date: 08-07-2024 Through 12-07-2024",

url = "https://compose.ioc.ee/icalp2024/",

}

Anand, K, Feng, W, Freifeld, G, Guo, H & Wang, J 2024, Approximate counting for spin systems in sub-quadratic time. in K Bringmann, M Grohe, G Puppis & O Svensson (eds), 51st International Colloquium on Automata, Languages, and Programming., 11, Leibniz International Proceedings in Informatics, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 1-20, 51st EATCS International Colloquium on Automata, Languages and Programming, Tallinn, Estonia, 8/07/24. https://doi.org/10.48550/arXiv.2306.14867, https://doi.org/10.4230/LIPIcs.ICALP.2024.11

Approximate counting for spin systems in sub-quadratic time. / Anand, Konrad; Feng, Weiming; Freifeld, Graham et al.
51st International Colloquium on Automata, Languages, and Programming. ed. / Karl Bringmann; Martin Grohe; Gabriele Puppis; Ola Svensson. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. p. 1-20 11 (Leibniz International Proceedings in Informatics).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Approximate counting for spin systems in sub-quadratic time

AU - Anand, Konrad

AU - Feng, Weiming

AU - Freifeld, Graham

AU - Guo, Heng

AU - Wang, Jiaheng

PY - 2024/7/2

Y1 - 2024/7/2

N2 - We present two randomised approximate counting algorithms with O˜(n2−c/ε2) 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−c1) where c1=c/(2−2c);(2) for spin systems with strong spatial mixing (SSM) on planar graphs with quadratic growth, such as Z2.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 Zd, but with a running time of the form O˜(n2ε−2/2c(logn)1/d) where d is the exponent of the polynomial growth and c>0 is some constant.

AB - We present two randomised approximate counting algorithms with O˜(n2−c/ε2) 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−c1) where c1=c/(2−2c);(2) for spin systems with strong spatial mixing (SSM) on planar graphs with quadratic growth, such as Z2.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 Zd, but with a running time of the form O˜(n2ε−2/2c(logn)1/d) where d is the exponent of the polynomial growth and c>0 is some constant.

KW - randomised algorithm

KW - approximate counting

KW - spin system

KW - sub-quadratic algorithm

U2 - 10.48550/arXiv.2306.14867

DO - 10.48550/arXiv.2306.14867

M3 - Conference contribution

T3 - Leibniz International Proceedings in Informatics

SP - 1

EP - 20

BT - 51st International Colloquium on Automata, Languages, and Programming

A2 - Bringmann, Karl

A2 - Grohe, Martin

A2 - Puppis, Gabriele

A2 - Svensson, Ola

PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik

T2 - 51st EATCS International Colloquium on Automata, Languages and Programming

Y2 - 8 July 2024 through 12 July 2024

ER -

Anand K, Feng W, Freifeld G, Guo H, Wang J. Approximate counting for spin systems in sub-quadratic time. In Bringmann K, Grohe M, Puppis G, Svensson O, editors, 51st International Colloquium on Automata, Languages, and Programming. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. 2024. p. 1-20. 11. (Leibniz International Proceedings in Informatics). doi: 10.48550/arXiv.2306.14867, 10.4230/LIPIcs.ICALP.2024.11

Approximate counting for spin systems in sub-quadratic time

Abstract / Description of output

Publication series

Conference

Keywords / Materials (for Non-textual outputs)

Access to Document

Fingerprint

Projects

NACS - New Approaches to Counting and Sampling

Cite this