License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2023.55
URN: urn:nbn:de:0030-drops-181070
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18107/
Go to the corresponding LIPIcs Volume Portal

Efthymiou, Charilaos ; Zampetakis, Kostas

Broadcasting with Random Matrices

pdf-format:
LIPIcs-ICALP-2023-55.pdf (0.6 MB)

Abstract

Motivated by the theory of spin-glasses in physics, we study the so-called reconstruction problem on the tree, and on the sparse random graph G(n,d/n). Both cases reduce naturally to analysing broadcasting models, where each edge has its own broadcasting matrix, and this matrix is drawn independently from a predefined distribution.
We establish the reconstruction threshold for the cases where the broadcasting matrices give rise to symmetric, 2-spin Gibbs distributions. This threshold seems to be a natural extension of the well-known Kesten-Stigum bound that manifests in the classic version of the reconstruction problem. Our results determine, as a special case, the reconstruction threshold for the prominent Edwards–Anderson model of spin-glasses, on the tree.
Also, we extend our analysis to the setting of the Galton-Watson random tree, and the (sparse) random graph G(n,d/n), where we establish the corresponding thresholds. Interestingly, for the Edwards–Anderson model on the random graph, we show that the replica symmetry breaking phase transition, established by Guerra and and Toninelli in [Guerra and Toninelli, 2004], coincides with the reconstruction threshold.
Compared to classical Gibbs distributions, spin-glasses have several unique features. In that respect, their study calls for new ideas, e.g. we introduce novel estimators for the reconstruction problem. The main technical challenge in the analysis of such systems, is the presence of (too) many levels of randomness, which we manage to circumvent by utilising recently proposed tools coming from the analysis of Markov chains.

BibTeX - Entry

@InProceedings{efthymiou_et_al:LIPIcs.ICALP.2023.55,
  author =	{Efthymiou, Charilaos and Zampetakis, Kostas},
  title =	{{Broadcasting with Random Matrices}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{55:1--55:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/18107},
  URN =		{urn:nbn:de:0030-drops-181070},
  doi =		{10.4230/LIPIcs.ICALP.2023.55},
  annote =	{Keywords: spin-system, spin-glass, sparse random graph, reconstruction, phase transitions}
}

Keywords: spin-system, spin-glass, sparse random graph, reconstruction, phase transitions
Collection: 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Issue Date: 2023
Date of publication: 05.07.2023

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