Approximate Counting for Spin Systems in Sub-Quadratic Time
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915102509236224 |
|---|---|
| author | Anand, Konrad Feng, Weiming Freifeld, Graham Guo, Heng Wang, Jiaheng |
| author_facet | Anand, Konrad Feng, Weiming Freifeld, Graham Guo, Heng Wang, Jiaheng |
| contents | We present two randomised approximate counting algorithms with $\widetilde{O}(n^{2-c}/\varepsilon^2)$ running time for some constant $c>0$ and accuracy $\varepsilon$:
(1) for the hard-core model with fugacity $λ$ on graphs with maximum degree $Δ$ when $λ=O(Δ^{-1.5-c_1})$ where $c_1=c/(2-2c)$;
(2) for spin systems with strong spatial mixing (SSM) on planar graphs with quadratic growth, such as $\mathbb{Z}^2$.
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 $\mathbb{Z}^d$, but with a running time of the form $\widetilde{O}\left(n^2\varepsilon^{-2}/2^{c(\log n)^{1/d}}\right)$ where $d$ is the exponent of the polynomial growth and $c>0$ is some constant. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2306_14867 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Approximate Counting for Spin Systems in Sub-Quadratic Time Anand, Konrad Feng, Weiming Freifeld, Graham Guo, Heng Wang, Jiaheng Data Structures and Algorithms We present two randomised approximate counting algorithms with $\widetilde{O}(n^{2-c}/\varepsilon^2)$ running time for some constant $c>0$ and accuracy $\varepsilon$: (1) for the hard-core model with fugacity $λ$ on graphs with maximum degree $Δ$ when $λ=O(Δ^{-1.5-c_1})$ where $c_1=c/(2-2c)$; (2) for spin systems with strong spatial mixing (SSM) on planar graphs with quadratic growth, such as $\mathbb{Z}^2$. 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 $\mathbb{Z}^d$, but with a running time of the form $\widetilde{O}\left(n^2\varepsilon^{-2}/2^{c(\log n)^{1/d}}\right)$ where $d$ is the exponent of the polynomial growth and $c>0$ is some constant. |
| title | Approximate Counting for Spin Systems in Sub-Quadratic Time |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2306.14867 |