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.APPROX-RANDOM.2017.40
URN: urn:nbn:de:0030-drops-75895
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7589/
Go to the corresponding LIPIcs Volume Portal

Coja-Oghlan, Amin ; Efthymiou, Charilaos ; Jaafari, Nor ; Kang, Mihyun ; Kapetanopoulos, Tobias

Charting the Replica Symmetric Phase

pdf-format:
LIPIcs-APPROX-RANDOM-2017-40.pdf (0.6 MB)

Abstract

Random graph models and associated inference problems such as the stochastic block model play an eminent role in computer science, discrete mathematics and statistics. Based on non-rigorous arguments physicists predicted the existence of a generic phase transition that separates a "replica symmetric phase" where statistical inference is impossible from a phase where the detection of the "ground truth" is information-theoretically possible.

In this paper we prove a contiguity result that shows that detectability is indeed impossible within the replica-symmetric phase for a broad class of models. In particular, this implies the detectability conjecture for the disassortative stochastic block model from [Decelle et al.: Phys Rev E 2011]. Additionally, we investigate key features of the replica symmetric phase such as the nature of point-to-set correlations (`reconstruction').

BibTeX - Entry

@InProceedings{cojaoghlan_et_al:LIPIcs:2017:7589,
  author =	{Amin Coja-Oghlan and Charilaos Efthymiou and Nor Jaafari and Mihyun Kang and Tobias Kapetanopoulos},
  title =	{{Charting the Replica Symmetric Phase}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)},
  pages =	{40:1--40:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-044-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{81},
  editor =	{Klaus Jansen and Jos{\'e} D. P. Rolim and David Williamson and Santosh S. Vempala},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7589},
  URN =		{urn:nbn:de:0030-drops-75895},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2017.40},
  annote =	{Keywords: Random factor graph, bounds for condensation phase transition, Potts antiferromagnet, diluted k-spin model, stochastic block model}
}

Keywords: Random factor graph, bounds for condensation phase transition, Potts antiferromagnet, diluted k-spin model, stochastic block model
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)
Issue Date: 2017
Date of publication: 11.08.2017

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