License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2020.37
URN: urn:nbn:de:0030-drops-127049
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12704/
Go to the corresponding LIPIcs Volume Portal

Galanis, Andreas ; Goldberg, Leslie Ann ; Stewart, James

Fast Algorithms for General Spin Systems on Bipartite Expanders

pdf-format:
LIPIcs-MFCS-2020-37.pdf (0.6 MB)

Abstract

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. 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 Õ(n²) time, where n is the size of the graph.

BibTeX - Entry

@InProceedings{galanis_et_al:LIPIcs:2020:12704,
  author =	{Andreas Galanis and Leslie Ann Goldberg and James Stewart},
  title =	{{Fast Algorithms for General Spin Systems on Bipartite Expanders}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{37:1--37:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Javier Esparza and Daniel Kr{\'a}ľ},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12704},
  URN =		{urn:nbn:de:0030-drops-127049},
  doi =		{10.4230/LIPIcs.MFCS.2020.37},
  annote =	{Keywords: bipartite expanders, approximate counting, spin systems}
}

Keywords: bipartite expanders, approximate counting, spin systems
Collection: 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)
Issue Date: 2020
Date of publication: 18.08.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI