H. Nishimori, Statistical Physics of Spin Glasses and Information Processing: An Introduction, 2001.

M. Mézard and A. Montanari, Information, Computation, 2009.

L. Zdeborová and F. Krzakala, Statistical physics of inference: thresholds and algorithms, Advances in Physics, vol.65, issue.5, pp.453-552, 2016.

A. S. Bandeira, A. Perry, and A. S. Wein, Notes on computational-to-statistical gaps: predictions using statistical physics, 2018.
DOI : 10.4171/pm/2014
URL : http://arxiv.org/pdf/1803.11132

C. Moore, The Computer Science and Physics of Community Detection: Landscapes, Phase Transitions, and Hardness, vol.1, 2017.

E. Abbe, Community detection and stochastic block models: recent developments, 2017.
DOI : 10.1561/0100000067

S. Fortunato, Community detection in graphs, Physics Reports, vol.486, pp.75-174, 2010.
DOI : 10.1016/j.physrep.2009.11.002
URL : http://arxiv.org/pdf/0906.0612v1.pdf

A. Decelle, F. Krzakala, C. Moore, and L. Zdeborová, Phase transition in the detection of modules in sparse networks, Phys. Rev. Lett, vol.107, p.65701, 2011.
URL : https://hal.archives-ouvertes.fr/hal-00625321

A. Decelle, F. Krzakala, C. Moore, and L. Zdeborová, Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications, Phys. Rev. E, vol.84, p.66106, 2011.
URL : https://hal.archives-ouvertes.fr/hal-00661643

F. Krzakala and L. Zdeborová, Hiding Quiet Solutions in Random Constraint Satisfaction Problems, Phys. Rev. Lett, vol.102, p.238701, 2009.
DOI : 10.1103/physrevlett.102.238701
URL : http://arxiv.org/pdf/0901.2130

L. Zdeborová and F. Krzakala, Quiet planting in the locked constraint satisfaction problems, SIAM Journal on Discrete Mathematics, vol.25, issue.2, pp.750-770, 2011.

E. Abbe and A. Montanari, Conditional Random Fields, Planted Constraint Satisfaction and Entropy Concentration, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pp.332-346, 2013.
DOI : 10.1007/978-3-642-40328-6_24

V. Feldman, W. Perkins, and S. Vempala, On the Complexity of Random Satisfiability Problems with Planted Solutions, Proceedings of the Forty-seventh Annual ACM Symposium on Theory of Computing, STOC '15, pp.77-86, 2015.

U. Feige, Relations Between Average Case Complexity and Approximation Complexity, Proceedings of the Thiry-fourth Annual ACM Symposium on Theory of Computing, STOC '02, pp.534-543, 2002.
DOI : 10.1145/509907.509985

W. Barthel, A. K. Hartmann, M. Leone, F. Ricci-tersenghi, M. Weigt et al., Hiding Solutions in Random Satisfiability Problems: A Statistical Mechanics Approach, Phys. Rev. Lett, vol.88, p.188701, 2002.
DOI : 10.1103/physrevlett.88.188701
URL : http://arxiv.org/pdf/cond-mat/0111153

T. Lesieur, F. Krzakala, and L. Zdeborová, Constrained low-rank matrix estimation: phase transitions, approximate message passing and applications, Journal of Statistical Mechanics: Theory and Experiment, issue.7, p.73403, 2017.
DOI : 10.1088/1742-5468/aa7284
URL : https://hal.archives-ouvertes.fr/cea-01447222

E. Mossel, Reconstruction on Trees: Beating the Second Eigenvalue, Ann. Appl. Probab, vol.11, issue.1, pp.285-300, 2001.
DOI : 10.1214/aoap/998926994
URL : https://doi.org/10.1214/aoap/998926994

S. Janson and E. Mossel, Robust reconstruction on trees is determined by the second eigenvalue, Ann. Probab, vol.32, pp.2630-2649, 2004.

M. Mézard and A. Montanari, Reconstruction on Trees and Spin Glass Transition, J. Stat. Phys, vol.124, pp.1317-1350, 2006.

C. Borgs, J. Chayes, E. Mossel, and S. Roch, The Kesten-Stigum Reconstruction Bound Is Tight for Roughly Symmetric Binary Channels, 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06), pp.518-530, 2006.
DOI : 10.1109/focs.2006.76

A. Sly, Reconstruction of Random Colourings, Communications in Mathematical Physics, vol.288, issue.3, pp.943-961, 2009.
DOI : 10.1007/s00220-009-0783-7
URL : https://link.springer.com/content/pdf/10.1007%2Fs00220-009-0783-7.pdf

A. Sly, Reconstruction for the Potts model, Ann. Probab, vol.39, issue.4, pp.1365-1406, 2011.
DOI : 10.1214/10-aop584
URL : https://doi.org/10.1214/10-aop584

F. Krzakala, A. Montanari, F. Ricci-tersenghi, G. Semerjian, and L. Zdeborová, Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems, Proc. Natl. Acad. Sci. U.S.A, vol.104, p.10318, 2007.
URL : https://hal.archives-ouvertes.fr/hal-00120473

A. Coja-oghlan, F. Krzakala, W. Perkins, and L. Zdeborová, Information-theoretic thresholds from the cavity method, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pp.146-157, 2017.
DOI : 10.1145/3055399.3055420
URL : https://hal.archives-ouvertes.fr/cea-01448087

A. Coja-oghlan, C. Efthymiou, N. Jaafari, M. Kang, and T. Kapetanopoulos, Charting the replica symmetric phase, Communications in Mathematical Physics, vol.359, issue.2, pp.603-698, 2018.
DOI : 10.1007/s00220-018-3096-x
URL : http://arxiv.org/pdf/1704.01043

J. Barbier, M. Dia, N. Macris, F. Krzakala, T. Lesieur et al., Mutual information for symmetric rank-one matrix estimation: A proof of the replica formula, Advances in Neural Information Processing Systems 29 (NIPS 2016), pp.424-432, 2016.
URL : https://hal.archives-ouvertes.fr/cea-01568705

F. Caltagirone, M. Lelarge, and L. Miolane, Recovering asymmetric communities in the stochastic block model, IEEE Transactions on Network Science and Engineering, 2017.
DOI : 10.1109/allerton.2016.7852204
URL : https://hal.archives-ouvertes.fr/hal-01963866

M. Lelarge and L. Miolane, Fundamental limits of symmetric low-rank matrix estimation, Proceedings of Machine Learning Research, vol.65, pp.1-5, 2017.
DOI : 10.1007/s00440-018-0845-x
URL : https://hal.archives-ouvertes.fr/hal-01648368

W. Liu and N. Ning, Reconstruction for the asymmetric Ising model on regular trees, 2017.

W. Liu, S. R. Jammalamadaka, and N. Ning, The Tightness of the Kesten-Stigum Reconstruction Bound of Symmetric Model with Multiple Mutations, Journal of Statistical Physics, pp.1-25, 2017.

D. L. Donoho, A. Maleki, and A. Montanari, Message-passing algorithms for compressed sensing, Proceedings of the National Academy of Sciences, vol.106, issue.45, pp.18914-18919, 2009.
DOI : 10.1073/pnas.0909892106
URL : http://www.pnas.org/content/106/45/18914.full.pdf

M. Bayati and A. Montanari, The Dynamics of Message Passing on Dense Graphs, with Applications to Compressed Sensing, IEEE Transactions on Information Theory, vol.57, issue.2, pp.764-785, 2011.

F. R. Kschischang, B. Frey, and H. Loeliger, Factor graphs and the sum-product algorithm, IEEE Trans. Inform. Theory, vol.47, issue.2, pp.498-519, 2001.
DOI : 10.1109/18.910572

H. Kesten and B. P. Stigum, Additional Limit Theorems for Indecomposable Multidimensional Galton-Watson Processes, The Annals of Mathematical Statistics, vol.37, p.1463, 1966.
DOI : 10.1214/aoms/1177699139
URL : https://doi.org/10.1214/aoms/1177699139

C. Measson, A. Montanari, and R. Urbanke, Maxwell Construction: The Hidden Bridge Between Iterative and Maximum a Posteriori Decoding, IEEE Transactions on Information Theory, vol.54, issue.12, pp.5277-5307, 2008.
DOI : 10.1109/tit.2008.2006466
URL : https://hal.archives-ouvertes.fr/hal-00290624

G. Parisi and F. Zamponi, Mean-field theory of hard sphere glasses and jamming, Reviews of Modern Physics, vol.82, issue.1, p.789, 2010.
DOI : 10.1103/revmodphys.82.789
URL : http://arxiv.org/pdf/0802.2180

J. R. De-almeida and D. J. Thouless, Stability of the Sherrington-Kirkpatrick Solution of a Spin-Glass Model, J. Phys. A, vol.11, pp.983-990, 1978.

M. Mézard, G. Parisi, and R. Zecchina, Analytic and Algorithmic Solution of Random Satisfiability Problems, Science, vol.297, pp.812-815, 2002.

S. E. Fienberg and S. S. Wasserman, Categorical data analysis of single sociometric relations, Sociological methodology, vol.12, pp.156-192, 1981.
DOI : 10.2307/270741

P. W. Holland, K. B. Laskey, and S. Leinhardt, Stochastic blockmodels: First steps, Social networks, vol.5, issue.2, pp.109-137, 1983.
DOI : 10.1016/0378-8733(83)90021-7

B. Bollobás, S. Janson, and O. Riordan, The phase transition in inhomogeneous random graphs. Random Structures & Algorithms, vol.31, pp.3-122, 2007.

E. Mossel, J. Neeman, and A. Sly, A proof of the block model threshold conjecture, Combinatorica, pp.1-44, 2013.

L. Massoulié, Community detection thresholds and the weak Ramanujan property, Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pp.694-703, 2014.

E. Mossel, J. Neeman, and A. Sly, Belief propagation, robust reconstruction and optimal recovery of block models, Ann. Appl. Probab, vol.26, issue.4, pp.2211-2256, 2016.
DOI : 10.1214/15-aap1145
URL : http://arxiv.org/pdf/1309.1380

E. Abbe and C. Sandon, Detection in the stochastic block model with multiple clusters: proof of the achievability conjectures, acyclic BP, and the information-computation gap, 2018.

L. Zdeborová and M. Mézard, Constraint satisfaction problems with isolated solutions are hard, J. Stat. Mech, p.12004, 2008.

M. C. Angelini, F. Caltagirone, F. Krzakala, and L. Zdeborová, Spectral detection on sparse hypergraphs, Communication, Control, and Computing (Allerton), 2015 53rd Annual Allerton Conference on, pp.66-73, 2015.
DOI : 10.1109/allerton.2015.7446987
URL : https://hal.archives-ouvertes.fr/cea-01330412

M. Mézard and G. Parisi, The Bethe lattice spin glass revisited, Eur. Phys. J. B, vol.20, p.217, 2001.

E. Mossel, J. Neeman, and A. Sly, Reconstruction and estimation in the planted partition model. Probability Theory and Related Fields, vol.162, pp.431-461, 2015.
DOI : 10.1007/s00440-014-0576-6

A. Coja-oghlan, T. Kapetanopoulos, and N. Müller, The replica symmetric phase of random constraint satisfaction problems, 2018.

P. M. Bleher, J. Ruiz, and V. A. Zagrebnov, On the purity of the limiting gibbs state for the Ising model on the Bethe lattice, Journal of Statistical Physics, vol.79, issue.1, pp.473-482, 1995.

W. Evans, C. Kenyon, Y. Peres, and L. J. Schulman, Broadcasting on trees and the Ising model, Ann. Appl. Probab, vol.10, pp.410-433, 2000.
DOI : 10.1214/aoap/1019487349
URL : https://doi.org/10.1214/aoap/1019487349

F. Krzakala and L. Zdeborová, Potts Glass on Random Graphs, Europhys. Lett, vol.81, p.57005, 2008.
URL : https://hal.archives-ouvertes.fr/hal-00304234

T. Lesieur, F. Krzakala, and L. Zdeborová, MMSE of probabilistic low-rank matrix estimation: Universality with respect to the output channel, Communication, Control, and Computing (Allerton), 2015 53rd Annual Allerton Conference on, pp.680-687, 2015.
URL : https://hal.archives-ouvertes.fr/cea-01222294

A. Montanari, Finding One Community in a Sparse Graph, Journal of Statistical Physics, vol.161, issue.2, pp.273-299, 2015.
DOI : 10.1007/s10955-015-1338-2
URL : http://arxiv.org/pdf/1502.05680

P. Zhang, C. Moore, and M. Newman, Community detection in networks with unequal groups, Physical Review E, vol.93, issue.1, p.12303, 2016.
DOI : 10.1103/physreve.93.012303
URL : https://link.aps.org/accepted/10.1103/PhysRevE.93.012303

M. Gabrié, V. Dani, G. Semerjian, and L. Zdeborová, Phase transitions in the q-coloring of random hypergraphs, Journal of Physics A: Mathematical and Theoretical, vol.50, issue.50, p.505002, 2017.

A. Montanari, Tight Bounds for LDPC and LDGM Codes Under MAP Decoding, IEEE Trans. Inform. Theory, vol.51, pp.3221-3246, 2005.
DOI : 10.1109/tit.2005.853320
URL : https://hal.archives-ouvertes.fr/hal-00290617

R. Abou-chacra, D. J. Thouless, and P. W. Anderson, A selfconsistent theory of localization, Journal of Physics C: Solid State Physics, vol.6, issue.10, p.1734, 1973.