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. arXiv:1512, p.9080, 2015.

D. Achlioptas and A. , Coja-Oghlan: Algorithmic barriers from phase transitions, Proc. 49th FOCS, pp.793-802, 2008.

D. Achlioptas, H. Hassani, N. Macris, and R. , Urbanke: Bounds for random constraint satisfaction problems via spatial coupling, Proc. 27th SODA, pp.469-479, 2016.

D. Achlioptas and C. Moore, ???SAT: Two Moments Suffice to Cross a Sharp Threshold, SIAM Journal on Computing, vol.36, issue.3, pp.740-762, 2006.
DOI : 10.1137/S0097539703434231

D. Achlioptas and C. Moore, On the 2-Colorability of Random Hypergraphs, Proc. 6th RANDOM, pp.78-90, 2002.
DOI : 10.1007/3-540-45726-7_7

D. Achlioptas and C. Moore, Almost all graphs with average degree 4 are 3-colorable, Journal of Computer and System Sciences, vol.67, issue.2, pp.441-471, 2003.
DOI : 10.1016/S0022-0000(03)00120-X

D. Achlioptas and A. Naor, The two possible values of the chromatic number of a random graph, Annals of Mathematics, vol.162, pp.1333-1349, 2005.

D. Achlioptas, A. Naor, and Y. , Rigorous location of phase transitions in hard optimization problems, Nature, vol.24, issue.7043, pp.759-764, 2005.
DOI : 10.1006/jagm.1996.0016

M. Aizenman, R. Sims, and S. Starr, Extended variational principle for the Sherrington-Kirkpatrick spin-glass model, Physical Review B, vol.68, issue.21, p.214403, 2003.
DOI : 10.1103/PhysRevB.68.214403

M. Alekhnovich, More on average case vs approximation complexity, 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings., pp.298-307, 2003.
DOI : 10.1109/SFCS.2003.1238204

N. Alon and N. , A Spectral Technique for Coloring Random 3-Colorable Graphs, SIAM Journal on Computing, vol.26, issue.6, pp.1733-1748, 1997.
DOI : 10.1137/S0097539794270248

N. Alon and M. Krivelevich, The concentration of the chromatic number of random graphs, Combinatorica, vol.7, issue.3, pp.303-313, 1997.
DOI : 10.1007/BF01215914

N. Alon, M. Krivelevich, and B. , Finding a large hidden clique in a random graph, Random Structures and Algorithms, vol.13, issue.3-4, pp.457-466, 1998.
DOI : 10.1002/(SICI)1098-2418(199810/12)13:3/4<457::AID-RSA14>3.0.CO;2-W

B. Applebaum, B. Barak, and A. , Wigderson: Public-key cryptography from different assumptions, Proceedings of the forty-second ACM symposium on Theory of computing, pp.171-180, 2010.
DOI : 10.1145/1806689.1806715

J. Banks, C. Moore, J. Neeman, and P. Netrapalli, Information-theoretic thresholds for community detection in sparse networks, Proc. 29th COLT, pp.383-416, 2016.

V. Bapst and A. , Harnessing the Bethe free energy, Random Structures & Algorithms, vol.9, issue.4, pp.694-741, 2016.
DOI : 10.1002/rsa.20692

V. Bapst, A. Coja-oghlan, and C. , Efthymiou: Planting colourings silently. Combinatorics, probability and computing

V. Bapst, A. Coja-oghlan, S. Hetterich, F. Rassmann, and D. , The Condensation Phase Transition in Random Graph Coloring, Communications in Mathematical Physics, vol.76, issue.26, pp.543-606, 2016.
DOI : 10.1007/s00220-015-2464-z

M. Bayati, D. Gamarnik, and P. Tetali, Combinatorial approach to the interpolation method and scaling limits in sparse random graphs, The Annals of Probability, vol.41, issue.6, pp.4080-4115, 2013.
DOI : 10.1214/12-AOP816

P. Billingsley, Convergence of probability measures, p.56, 1999.
DOI : 10.1002/9780470316962

B. Bollobás, The chromatic number of random graphs, Combinatorica, vol.5, issue.1, pp.49-55, 1988.
DOI : 10.1007/BF02122551

B. Bollobás, S. Janson, and O. Riordan, The phase transition in inhomogeneous random graphs, Random Structures and Algorithms, vol.123, issue.1, pp.3-122, 2007.
DOI : 10.1002/rsa.20168

R. Boppana, Eigenvalues and graph bisection: An average-case analysis, 28th Annual Symposium on Foundations of Computer Science (sfcs 1987), pp.280-285, 1987.
DOI : 10.1109/SFCS.1987.22

C. Bordenave, M. Lelarge, and L. , Massoulié: Non-backtracking spectrum of random graphs: community detection and non-regular Ramanujan graphs, Proc. 56th FOCS, pp.1347-1357, 2015.

J. Cheng and R. Mceliece, Some high-rate near capacity codecs for the Gaussian channel, Proc, p.34, 1996.

A. Coja-oghlan, Graph Partitioning via Adaptive Spectral Techniques, Combinatorics, Probability and Computing, vol.51, issue.02, pp.227-284, 2010.
DOI : 10.1137/S0097539794270248

A. Coja-oghlan, Upper-bounding the k-colorability threshold by counting covers, Electronic Journal of Combinatorics, vol.20, p.32, 2013.

A. Coja-oghlan and N. Jaafari, On the Potts model on random graphs, Electronic Journal of Combinatorics, vol.23, 2016.

A. Coja-oghlan and K. , The asymptotic k-SAT threshold, Advances in Mathematics, vol.288, pp.985-1068, 2016.
DOI : 10.1016/j.aim.2015.11.007

A. Coja-oghlan and W. Perkins, Belief Propagation on replica symmetric random factor graph models, Proc. 20th RANDOM, pp.1-27, 2016.

A. Coja-oghlan, W. Perkins, and K. , Skubch: Limits of discrete distributions and Gibbs measures on random graphs, 2015.

P. Contucci, S. Dommers, C. Giardina, and S. Starr, Antiferromagnetic Potts Model on the Erd??s-R??nyi Random Graph, Communications in Mathematical Physics, vol.76, issue.3, pp.517-554, 2013.
DOI : 10.1007/s00220-013-1778-y

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

A. Dembo and A. , Gibbs measures and phase transitions on sparse random graphs, Brazilian Journal of Probability and Statistics, vol.24, issue.2, pp.137-211, 2010.
DOI : 10.1214/09-BJPS027

A. Dembo, A. Montanari, A. Sly, and N. , The Replica Symmetric Solution for Potts Models on d-Regular Graphs, Communications in Mathematical Physics, vol.11, issue.4, pp.551-575, 2014.
DOI : 10.1007/s00220-014-1956-6

A. Dembo, A. Montanari, and N. , Factor models on locally tree-like graphs, The Annals of Probability, vol.41, issue.6, pp.4162-4213, 2013.
DOI : 10.1214/12-AOP828

Y. Deshpande, E. Abbe, and A. Montanari, Asymptotic mutual information for the two-groups stochastic block model, 2015.

J. Ding, A. Sly, and N. , Satisfiability Threshold for Random Regular nae-sat, Communications in Mathematical Physics, vol.5, issue.2, pp.435-489, 2016.
DOI : 10.1007/s00220-015-2492-8

J. Ding, A. Sly, and N. , Sun: Maximum independent sets on random regular graphs. arXiv:1310, p.4787, 2013.

J. Ding, A. Sly, and N. , Sun: Proof of the satisfiability conjecture for large k, Proc. 47th STOC, pp.59-68, 2015.

P. Erd?-os and A. Rényi, On the evolution of random graphs, Magyar Tud. Akad. Mat. Kutató Int. Közl, vol.5, pp.17-61, 1960.

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

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

S. Franz and M. Leone, Replica bounds for optimization problems and diluted spin systems, Journal of Statistical Physics, vol.111, issue.3/4, pp.535-564, 2003.
DOI : 10.1023/A:1022885828956

A. Giurgiu, N. Macris, and R. , Spatial Coupling as a Proof Technique and Three Applications, IEEE Transactions on Information Theory, vol.62, issue.10, pp.5281-5295, 2016.
DOI : 10.1109/TIT.2016.2539144

M. Dyer, A. Frieze, and C. , On the chromatic number of a random hypergraph, Journal of Combinatorial Theory, Series B, vol.113, pp.68-122, 2015.
DOI : 10.1016/j.jctb.2015.01.002

O. Guédon and R. Vershynin, Community detection in sparse networks via Grothendieck's inequality. Probability Theory and Related Fields, pp.1-25, 2015.

F. Guerra, Broken Replica Symmetry Bounds in the Mean Field Spin Glass Model, Communications in Mathematical Physics, vol.233, issue.1, pp.1-12, 2003.
DOI : 10.1007/s00220-002-0773-5

P. Holland, K. 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

Y. Kabashima and D. Saad, Statistical mechanics of error-correcting codes, Europhysics Letters (EPL), vol.45, issue.1, pp.97-103, 1999.
DOI : 10.1209/epl/i1999-00137-2

M. Krivelevich and B. Sudakov, The chromatic numbers of random hypergraphs. Random structures and algorithms, pp.381-403, 1998.

F. Krzakala and L. Zdeborová, Hiding Quiet Solutions in Random Constraint Satisfaction Problems, Physical Review Letters, vol.102, issue.23, 2009.
DOI : 10.1103/PhysRevLett.102.238701

F. Krzakala, A. Montanari, F. Ricci-tersenghi, G. Semerjian, and L. , Gibbs states and the set of solutions of random constraint satisfaction problems, Proceedings of the National Academy of Sciences, vol.104, issue.25, pp.10318-10323, 2007.
DOI : 10.1073/pnas.0703685104
URL : https://hal.archives-ouvertes.fr/hal-00120473

F. Krzakala, J. Xu, and L. , Zdeborová: Mutual Information in Rank-One Matrix Estimation, 2016.

S. Kudekar, T. Richardson, and R. , Spatially Coupled Ensembles Universally Achieve Capacity Under Belief Propagation, IEEE Transactions on Information Theory, vol.59, issue.12, pp.7761-7813, 2013.
DOI : 10.1109/TIT.2013.2280915

K. Kumar, P. Pakzad, A. Salavati, and A. Shokrollahi, Phase Transitions for Mutual Information, 2010 6th International Symposium on Turbo Codes & Iterative Information Processing, pp.137-141, 2010.
DOI : 10.1109/ISTC.2010.5613821

M. Lelarge and L. , Miolane: Fundamental limits of symmetric low-rank matrix estimation, 2016.

T. ?uczak, The chromatic number of random graphs, Combinatorica, vol.7, issue.1, pp.45-54, 1991.
DOI : 10.1007/BF01375472

F. Mcsherry, Spectral partitioning of random graphs, Proceedings 2001 IEEE International Conference on Cluster Computing, pp.529-537, 2001.
DOI : 10.1109/SFCS.2001.959929

N. Macris, Griffith&ndash;Kelly&ndash;Sherman Correlation Inequalities: A Useful Tool in the Theory of Error Correcting Codes, IEEE Transactions on Information Theory, vol.53, issue.2, pp.664-683, 2007.
DOI : 10.1109/TIT.2006.889002

L. Massoulié, Community detection thresholds and the weak Ramanujan property, Proceedings of the 46th Annual ACM Symposium on Theory of Computing, STOC '14, pp.694-703, 2014.
DOI : 10.1145/2591796.2591857

C. Méasson, A. Montanari, T. Richardson, and R. , The Generalized Area Theorem and Some of its Consequences, IEEE Transactions on Information Theory, vol.55, issue.11, pp.4793-4821, 2009.
DOI : 10.1109/TIT.2009.2030457

C. Méasson, A. Montanari, and R. Urbanke, Maxwell Construction: The Hidden Bridge Between Iterative and Maximum <emphasis emphasistype="italic">a Posteriori</emphasis> Decoding, IEEE Transactions on Information Theory, vol.54, issue.12, pp.5277-5307, 2008.
DOI : 10.1109/TIT.2008.2006466

M. Mézard and A. , Montanari: Information, physics and computation, 2009.

M. Mézard and G. Parisi, The Bethe lattice spin glass revisited, The European Physical Journal B, vol.20, issue.2, pp.217-233, 2001.
DOI : 10.1007/PL00011099

M. Mézard and G. Parisi, The cavity method at zero temperature, Journal of Statistical Physics, vol.111, issue.1/2, pp.1-34, 2003.
DOI : 10.1023/A:1022221005097

M. Mézard, G. Parisi, and M. , Virasoro: Spin glass theory and beyond, World Scientific, 1987.

M. Mézard, G. Parisi, and R. Zecchina, Analytic and Algorithmic Solution of Random Satisfiability Problems, Science, vol.297, issue.5582, pp.812-815, 2002.
DOI : 10.1126/science.1073287

M. Molloy, The freezing threshold for k-colourings of a random graph, Proceedings of the 44th symposium on Theory of Computing, STOC '12, pp.921-930, 2012.
DOI : 10.1145/2213977.2214060

R. Monasson, Optimization problems and replica symmetry breaking in finite connectivity spin glasses, Journal of Physics A: Mathematical and General, vol.31, issue.2, p.31, 1998.
DOI : 10.1088/0305-4470/31/2/012

A. Montanari, Tight Bounds for LDPC and LDGM Codes Under MAP Decoding, IEEE Transactions on Information Theory, vol.51, issue.9, pp.3221-3246, 2005.
DOI : 10.1109/TIT.2005.853320
URL : https://hal.archives-ouvertes.fr/hal-00290617

A. Montanari, Estimating random variables from random sparse observations, European Transactions on Telecommunications, vol.19, pp.385-403, 2008.
URL : https://hal.archives-ouvertes.fr/hal-00290792

A. Montanari, R. Restrepo, and P. Tetali, Reconstruction and Clustering in Random Constraint Satisfaction Problems, SIAM Journal on Discrete Mathematics, vol.25, issue.2, pp.771-808, 2011.
DOI : 10.1137/090755862

A. Montanari and S. Sen, Semidefinite programs on sparse random graphs and their application to community detection, Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, pp.814-827, 2016.
DOI : 10.1145/2897518.2897548

E. Mossel, J. Neeman, and A. , Sly: A proof of the block model threshold conjecture, 2013.

E. Mossel, J. Neeman, and A. Sly, Reconstruction and estimation in the planted partition model. Probability Theory and Related Fields, pp.1-31, 2014.

R. Neininger and L. , Rüschendorf: A general limit theorem for recursive algorithms and combinatorial structures, The Annals of Applied Probability, vol.14, pp.378-418, 2004.

D. Panchenko, The Sherrington-Kirkpatrick model, 2013.
DOI : 10.1007/978-1-4614-6289-7

D. Panchenko, Spin glass models from the point of view of spin distributions, The Annals of Probability, vol.41, issue.3A, pp.1315-1361, 2013.
DOI : 10.1214/11-AOP696

D. Panchenko and M. Talagrand, Bounds for diluted mean-fields spin glass models, Probability Theory and Related Fields, vol.337, issue.3, pp.319-336, 2004.
DOI : 10.1007/s00440-004-0342-2

S. Rachev, Probability metrics and the stability of stochastic models, 1991.

A. Sly, N. Sun, and Y. , Zhang: The number of solutions for random regular NAE-SAT, 2016.

M. Talagrand, The Parisi formula, Annals of Mathematics, vol.163, issue.1, pp.221-263, 2006.
DOI : 10.4007/annals.2006.163.221

C. Villani, Optimal transport: old and new, 2009.
DOI : 10.1007/978-3-540-71050-9

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

L. Zdeborová and F. Krzakala, Phase transitions in the coloring of random graphs, Physical Review E, vol.76, issue.3, p.31131, 2007.
DOI : 10.1103/PhysRevE.76.031131