DROPS

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2023.55

Broadcasting with Random Matrices

Authors: Charilaos Efthymiou and Kostas Zampetakis

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

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.

Cite as

Charilaos Efthymiou and Kostas Zampetakis. Broadcasting with Random Matrices. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 55:1-55:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@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/entities/document/10.4230/LIPIcs.ICALP.2023.55},
  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}
}

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2021.8

Local Approximations of the Independent Set Polynomial

Authors: Dimitris Achlioptas and Kostas Zampetakis

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract

The independent set polynomial of a graph has one variable for each vertex and one monomial for each independent set, comprising the product of the corresponding variables. Given a graph G on n vertices and a vector p ∈ [0,1)ⁿ, a central problem in statistical mechanics is determining whether the independent set polynomial of G is non-vanishing in the polydisk of p, i.e., whether |Z_G(x)| > 0 for every x ∈ ℂⁿ such that |x_i| ≤ p_i. Remarkably, when this holds, Z_G(-p) is a lower bound for the avoidance probability when G is a dependency graph for n events whose probabilities form vector p. A local sufficient condition for |Z_G| > 0 in the polydisk of p is the Lovász Local Lemma (LLL). In this work we derive several new results on the efficient evaluation and bounding of Z_G. Our starting point is a monotone mapping from subgraphs of G to truncations of the tree of self-avoiding walks of G. Using this mapping our first result is a local upper bound for Z(-p), similar in spirit to the local lower bound for Z(-p) provided by the LLL. Next, using this mapping, we show that when G is chordal, Z_G can be computed exactly and in linear time on the entire complex plane, implying perfect sampling for the hard-core model on chordal graphs. We also revisit the task of bounding Z(-p) from below, i.e., the LLL setting, and derive four new lower bounds of increasing sophistication. Already our simplest (and weakest) bound yields a strict improvement of the famous asymmetric LLL, i.e., a strict relaxation of the inequalities of the asymmetric LLL without any further assumptions. This new asymmetric local lemma is sharp enough to recover Shearer’s optimal bound in terms of the maximum degree Δ(G). We also apply our more sophisticated bounds to estimate the zero-free region of the hard-core model on the triangular lattice (hard hexagons model).

Cite as

Dimitris Achlioptas and Kostas Zampetakis. Local Approximations of the Independent Set Polynomial. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 8:1-8:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{achlioptas_et_al:LIPIcs.ICALP.2021.8,
  author =	{Achlioptas, Dimitris and Zampetakis, Kostas},
  title =	{{Local Approximations of the Independent Set Polynomial}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{8:1--8:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.8},
  URN =		{urn:nbn:de:0030-drops-140773},
  doi =		{10.4230/LIPIcs.ICALP.2021.8},
  annote =	{Keywords: Independent Set Polynomial, Lov\'{a}sz Local Lemma, Self-avoiding Walks}
}

Search Results

Documents authored by Zampetakis, Kostas

Broadcasting with Random Matrices

Abstract

Cite as

Local Approximations of the Independent Set Polynomial

Abstract

Cite as

Thanks for your feedback!

Could not send message