Approximate Counting for Spin Systems in Sub-Quadratic Time
OPEN ACCESS
Loading...
Author / Producer
Date
2024-07
Publication Type
Conference Paper
ETH Bibliography
yes
Citations
Altmetric
OPEN ACCESS
Data
Rights / License
Abstract
We present two randomised approximate counting algorithms with Oe(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(log n)1/d) where d is the exponent of the polynomial growth and c > 0 is some constant.
Permanent link
Publication status
published
Book title
51st International Colloquium on Automata, Languages, and Programming
Volume
297
Pages / Article No.
Publisher
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Event
51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Randomised algorithm; Approximate counting; Spin system; Sub-quadratic algorithm
Organisational unit
02889 - ETH Institut für Theoretische Studien / ETH Institute for Theoretical Studies