2026-07-20T05:31:25Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7589 2024-03-06T10:40:41Z ddc:004 open_access

Charting the Replica Symmetric Phase Coja-Oghlan, Amin Efthymiou, Charilaos Jaafari, Nor Kang, Mihyun Kapetanopoulos, Tobias Random factor graph bounds for condensation phase transition Potts antiferromagnet diluted k-spin model stochastic block model 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'). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Amin Coja-Oghlan and Charilaos Efthymiou and Nor Jaafari and Mihyun Kang and Tobias Kapetanopoulos 2017 Is Part Of LIPIcs, Volume 81, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2017.40 urn:nbn:de:0030-drops-75895 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2017.40 eng https://creativecommons.org/licenses/by/3.0/legalcode