Fast algorithms for general spin systems on bipartite expanders
A spin system is a framework in which the vertices of a graph are assigned spins from a finite set. The interactions between neighbouring spins give rise to weights, so a spin assignment can also be viewed as a weighted graph homomorphism. The problem of approximating the partition function (the agg...
| Main Authors: | , , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
Association for Computing Machinery
2021
|
| _version_ | 1797080383564546048 |
|---|---|
| author | Galanis, A Goldberg, L Stewart, J |
| author_facet | Galanis, A Goldberg, L Stewart, J |
| author_sort | Galanis, A |
| collection | OXFORD |
| description | A spin system is a framework in which the vertices of a graph are assigned spins
from a finite set. The interactions between neighbouring spins give rise to weights, so a
spin assignment can also be viewed as a weighted graph homomorphism. The problem
of approximating the partition function (the aggregate weight of spin assignments) or of
sampling from the resulting probability distribution is typically intractable for general
graphs.
In this work, we consider arbitrary spin systems on bipartite expander ∆-regular
graphs, including the canonical class of bipartite random ∆-regular graphs. We develop
fast approximate sampling and counting algorithms for general spin systems whenever the
degree and the spectral gap of the graph are sufficiently large. Roughly, this guarantees
that the spin system is in the so-called low-temperature regime. Our approach generalises
the techniques of Jenssen et al. and Chen et al. by showing that typical configurations
on bipartite expanders correspond to “bicliques” of the spin system; then, using suitable polymer models, we show how to sample such configurations and approximate the
partition function in O˜(n
2
) time, where n is the size of the graph. |
| first_indexed | 2024-03-07T00:59:14Z |
| format | Journal article |
| id | oxford-uuid:8923d22c-0179-454a-a720-cc8672ad18c0 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T00:59:14Z |
| publishDate | 2021 |
| publisher | Association for Computing Machinery |
| record_format | dspace |
| spelling | oxford-uuid:8923d22c-0179-454a-a720-cc8672ad18c02022-03-26T22:22:28ZFast algorithms for general spin systems on bipartite expandersJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:8923d22c-0179-454a-a720-cc8672ad18c0EnglishSymplectic ElementsAssociation for Computing Machinery2021Galanis, AGoldberg, LStewart, JA spin system is a framework in which the vertices of a graph are assigned spins from a finite set. The interactions between neighbouring spins give rise to weights, so a spin assignment can also be viewed as a weighted graph homomorphism. The problem of approximating the partition function (the aggregate weight of spin assignments) or of sampling from the resulting probability distribution is typically intractable for general graphs. In this work, we consider arbitrary spin systems on bipartite expander ∆-regular graphs, including the canonical class of bipartite random ∆-regular graphs. We develop fast approximate sampling and counting algorithms for general spin systems whenever the degree and the spectral gap of the graph are sufficiently large. Roughly, this guarantees that the spin system is in the so-called low-temperature regime. Our approach generalises the techniques of Jenssen et al. and Chen et al. by showing that typical configurations on bipartite expanders correspond to “bicliques” of the spin system; then, using suitable polymer models, we show how to sample such configurations and approximate the partition function in O˜(n 2 ) time, where n is the size of the graph. |
| spellingShingle | Galanis, A Goldberg, L Stewart, J Fast algorithms for general spin systems on bipartite expanders |
| title | Fast algorithms for general spin systems on bipartite expanders |
| title_full | Fast algorithms for general spin systems on bipartite expanders |
| title_fullStr | Fast algorithms for general spin systems on bipartite expanders |
| title_full_unstemmed | Fast algorithms for general spin systems on bipartite expanders |
| title_short | Fast algorithms for general spin systems on bipartite expanders |
| title_sort | fast algorithms for general spin systems on bipartite expanders |
| work_keys_str_mv | AT galanisa fastalgorithmsforgeneralspinsystemsonbipartiteexpanders AT goldbergl fastalgorithmsforgeneralspinsystemsonbipartiteexpanders AT stewartj fastalgorithmsforgeneralspinsystemsonbipartiteexpanders |