The Library
Broadcasting with random matrices
Tools
Efthymiou, Charilaos and Zampetakis, Kostas (2023) Broadcasting with random matrices. In: 50th EATCS International Colloquium on Automata, Languages and Programming, ICALP 2023, Paderborn, Germany, 10-14 Jul 2023. Published in: Leibniz International Proceedings in Informatics (LIPIcs) 55:1-55:14. doi:10.4230/LIPIcs.ICALP.2023.55 ISSN 1868-8969.
|
PDF
LIPIcs-ICALP-2023-55.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (636Kb) | Preview |
|
PDF
BroadcastingRandomMatrices2023-02-22.pdf - Accepted Version Embargoed item. Restricted access to Repository staff only - Requires a PDF viewer. Download (414Kb) |
Official URL: https://doi.org/10.4230/LIPIcs.ICALP.2023.55
Abstract
Motivated by the theory of spin-glasses in physics, we study the so-called reconstruction problem for the related distributions on the tree, and on the sparse random graph G(n,d/n).
Both cases, reduce naturally to studying broadcasting models on the tree, where each edge has its own broadcasting matrix, and this matrix is drawn independently from a predefined distribution. In this context, we study the effect of the configuration at the root to that of the vertices at distance h, as h\to\infty.
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 which arises in the classic version of the reconstruction problem.
Our results imply, as a special case, the reconstruction threshold for the well-known Edward-Anderson model of spin-glasses on the tree. Also, we extend our analysis to the setting of the Galton-Watson tree, and the random graph G(n,d/n), where we establish the corresponding thresholds. Interestingly, for the Edward-Anderson model on the random graph, we show that the replica symmetry breaking phase transition, established in [Guerra and Toninelli:2004], coincides with the reconstruction threshold.
Compared to the classical Gibbs distributions, the spin-glasses have a lot of unique features. In that respect, their study calls for new ideas, e.g., here we introducing novel estimators for the reconstruction problem. Furthermore, note that the main technical challenge in the analysis is the presence of (too) many levels of randomness. We manage to circumvent this problem by utilising recently proposed tools coming from the analysis of Markov chains.
Item Type: | Conference Item (Paper) | ||||||
---|---|---|---|---|---|---|---|
Subjects: | Q Science > QC Physics | ||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||
Library of Congress Subject Headings (LCSH): | Reconstruction (Graph theory), Spin glasses, Random graphs | ||||||
Journal or Publication Title: | Leibniz International Proceedings in Informatics (LIPIcs) | ||||||
Publisher: | Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik | ||||||
ISSN: | 1868-8969 | ||||||
Official Date: | 5 July 2023 | ||||||
Dates: |
|
||||||
Page Range: | 55:1-55:14 | ||||||
DOI: | 10.4230/LIPIcs.ICALP.2023.55 | ||||||
Status: | Peer Reviewed | ||||||
Publication Status: | Published | ||||||
Access rights to Published version: | Open Access (Creative Commons) | ||||||
Date of first compliant deposit: | 25 April 2023 | ||||||
Date of first compliant Open Access: | 14 July 2023 | ||||||
Grant number: | |||||||
RIOXX Funder/Project Grant: |
|
||||||
Conference Paper Type: | Paper | ||||||
Title of Event: | 50th EATCS International Colloquium on Automata, Languages and Programming, ICALP 2023 | ||||||
Type of Event: | Conference | ||||||
Location of Event: | Paderborn, Germany | ||||||
Date(s) of Event: | 10-14 Jul 2023 | ||||||
Related URLs: | |||||||
Open Access Version: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year