A. Stephen and . Cook, The complexity of theorem-proving procedures, Proceedings of the third annual ACM symposium on Theory of computing, pp.151-158, 1971.

P. Cheeseman, B. Kanefsky, M. William, and . Taylor, Where the really hard problems are, IJCAI, pp.331-337, 1991.

D. Mitchell, B. Selman, and H. Levesque, Hard and easy distributions of sat problems, AAAI, pp.459-465, 1992.

M. Mézard, G. Parisi, and M. A. Virasoro, Spin- Glass Theory and Beyond, Lecture Notes in Physics. World Scientific, vol.9, 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

S. Mertens, M. Mézard, and R. Zecchina, Threshold values of randomK-SAT from the cavity method, Random Structures and Algorithms, vol.42, issue.17, pp.340-373, 2006.
DOI : 10.1002/rsa.20090

R. Monasson, R. Zecchina, S. Kirkpatrick, B. Selman, and L. Troyansky, 2+p-sat: Relation of typical-case complexity to the nature of the phase transition. Random Structures and Algorithms, p.414, 1999.

G. Biroli, R. Monasson, and M. Weigt, A variational description of the ground state structure in random satisfiability problems, The European Physical Journal B, vol.14, issue.3, p.551, 2000.
DOI : 10.1007/s100510051065

F. Krzakala, A. Montanari, F. Ricci-tersenghi, G. Semerjian, and L. Zdeborova, Gibbs states and the set of solutions of random constraint satisfaction problems, Proceedings of the National Academy of Sciences, pp.10318-10323, 2007.
DOI : 10.1214/aoap/1060202828
URL : https://hal.archives-ouvertes.fr/hal-00120473

M. Mézard, T. Mora, and R. Zecchina, Clustering of Solutions in the Random Satisfiability Problem, Physical Review Letters, vol.264, issue.19, p.197205, 2005.
DOI : 10.1103/PhysRevLett.90.047205

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 F. Ricci-tersenghi, On the solution-space geometry of random constraint satisfaction problems, Proc. of 38th STOC, pp.130-139, 2006.

D. Achlioptas and A. Coja-oghlan, Algorithmic Barriers from Phase Transitions, 2008 49th Annual IEEE Symposium on Foundations of Computer Science, p.793, 2008.
DOI : 10.1109/FOCS.2008.11

J. Ding, A. Sly, and N. Sun, Proof of the satisfiability conjecture for large k. arXiv preprint, 2014.

R. Mulet, A. Pagnani, M. Weigt, and R. Zecchina, Coloring random graphs. Physical review letters, p.268701, 2002.

F. Krzakala, A. Pagnani, and M. Weigt, Threshold values, stability analysis, and high-q asymptotics for the coloring problem on random graphs, Physical Review E -Statistical, Nonlinear, and Soft Matter Physics, 2004.

L. Zdeborová and F. Krzakala, Phase transitions in the coloring of random graphs, Physical Review E, vol.46, issue.3, 2007.
DOI : 10.1140/epjb/e2005-00293-1

A. Sly, Reconstruction of Random Colourings, Communications in Mathematical Physics, vol.76, issue.6, pp.943-961, 2009.
DOI : 10.1007/s00220-009-0783-7

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

A. Coja-oghlan and D. Vilenchik, Chasing the kcolorability threshold, Foundations of Computer Science (FOCS), 2013 IEEE 54th Annual Symposium on, pp.380-389, 2013.

V. Bapst, A. Coja-oghlan, S. Hetterich, F. Raßmann, and D. Vilenchik, The Condensation Phase Transition in Random Graph Coloring, Communications in Mathematical Physics, vol.76, issue.26, pp.543-606, 2016.
DOI : 10.1103/PhysRevE.76.031131

A. Sly and Y. Zhang, Reconstruction of colourings without freezing. ArXiv e-prints, 2016.

V. Dani, C. Moore, and A. Olson, Tight Bounds on the Threshold for Permuted k-Colorability, Approximation, Randomization, and Combinatorial Optimization . Algorithms and Techniques, pp.505-516, 2012.
DOI : 10.1007/978-3-642-32512-0_43

T. Castellani, V. Napolano, F. Ricci-tersenghi, and R. Zecchina, Bicolouring random hypergraphs, Journal of Physics A: Mathematical and General, vol.36, issue.43, p.11037, 2003.
DOI : 10.1088/0305-4470/36/43/026

L. Dall-'asta, A. Ramezanpour, and R. Zecchina, Entropy landscape and non-Gibbs solutions in constraint satisfaction problems, Physical Review E -Statistical, Nonlinear, and Soft Matter Physics, 2008.

A. Braunstein, L. Dall-'asta, G. Semerjian, and L. Zdeborová, The large deviations of the whitening process in random constraint satisfaction problems, Journal of Statistical Mechanics: Theory and Experiment, vol.2016, issue.5, p.2016053401, 2016.
DOI : 10.1088/1742-5468/2016/05/053401

A. Coja-oghlan and L. Zdeborova, The condensation transition in random hypergraph 2-coloring, Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, pp.241-250, 2012.
DOI : 10.1137/1.9781611973099.22

A. Coja-oglan and K. Panagiotou, Catching the k-NAESAT threshold, Proceedings of the 44th symposium on Theory of Computing, STOC '12, pp.899-908, 2012.
DOI : 10.1145/2213977.2214058

J. Ding, A. Sly, and N. Sun, Satisfiability Threshold for Random Regular nae-sat, Communications in Mathematical Physics, vol.5, issue.2, pp.435-489, 2016.
DOI : 10.1017/CBO9780511721335.010

M. Molloy and R. Restrepo, Frozen variables in random boolean constraint satisfaction problems, Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp.1306-1318, 2013.
DOI : 10.1137/1.9781611973105.95

V. Bapst, A. Coja-oghlan, and F. Rassmann, A positive temperature phase transition in random hypergraph 2-coloring. arXiv preprint arXiv, 1410.

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

M. Dyer, A. Frieze, and C. Greenhill, 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

P. Ayre, A. Coja-oghlan, and C. Greenhill, Hypergraph coloring up to condensation. arXiv preprint, 2015.

A. Montanari, G. Parisi, and F. Ricci-tersenghi, Instability of one-step replica-symmetry-broken phase in satisfiability problems, Journal of Physics A: Mathematical and General, vol.37, issue.6, p.2073, 2004.
DOI : 10.1088/0305-4470/37/6/008
URL : https://hal.archives-ouvertes.fr/hal-00008647

L. Berthier and G. Biroli, Theoretical perspective on the glass transition and amorphous materials, Reviews of Modern Physics, vol.2, issue.2, pp.587-645, 2011.
DOI : 10.1103/PhysRevB.73.172203
URL : https://hal.archives-ouvertes.fr/hal-00608672

A. Montanari, F. Ricci-tersenghi, and G. Semerjian, Clusters of solutions and replica symmetry breaking in random k-satisfiability, Journal of Statistical Mechanics: Theory and Experiment, issue.04, p.4004, 2008.
URL : https://hal.archives-ouvertes.fr/hal-00259131

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

A. Coja-oghlan, F. Krzakala, W. Perkins, and L. Zdeborova, Information-theoretic thresholds from the cavity method, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing , STOC 2017, 2016.
DOI : 10.1103/PhysRevE.76.031131
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, 2017.

S. Franz and M. Leone, Replica bounds for optimization problems and diluted spin systems, J. Stat. Phys, pp.3-4, 2003.

D. Panchenko and M. Talagrand, Bounds for diluted mean-fields spin glass models. Probability Theory and Related Fields, pp.319-336, 2004.

M. Mézard and A. Montanari, Reconstruction on Trees and Spin Glass Transition, Journal of Statistical Physics, vol.37, issue.6, pp.1317-1350, 2006.
DOI : 10.1007/s10955-006-9162-3

A. Montanari and F. Ricci-tersenghi, On the nature of the low-temperature phase in discontinuous mean-field spin glasses, The European Physical Journal B - Condensed Matter, vol.33, issue.3, pp.339-346, 2003.
DOI : 10.1140/epjb/e2003-00174-7

O. Rivoire, G. Biroli, O. C. Martin, and M. Mézard, Glass models on Bethe lattices, The European Physical Journal B - Condensed Matter, vol.37, issue.1, pp.55-78, 2004.
DOI : 10.1140/epjb/e2004-00030-4
URL : https://hal.archives-ouvertes.fr/hal-00002292

L. Zdeborova, Constraint satisfaction problems, Random graphs coloring problem, Average computational complexity, Cavity method, Spin glasses, Acta Physica Slovaca, vol.59, issue.3, pp.169-303, 2009.

A. Montanari and G. Semerjian, On the Dynamics of the Glass Transition on Bethe Lattices, Journal of Statistical Physics, vol.47, issue.14, pp.103-189, 2006.
DOI : 10.1007/s10955-006-9103-1
URL : https://hal.archives-ouvertes.fr/hal-00285116

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

S. Janson and E. Mossel, Robust reconstruction on trees is determined by the second eigenvalue

T. Lesieur, L. Miolane, M. Lelarge, F. Krzakala, and L. Zdeborová, Statistical and computational phase transitions in spiked tensor estimation. ArXiv e-prints, 2017.
URL : https://hal.archives-ouvertes.fr/cea-01555504

G. Parisi, Infinite Number of Order Parameters for Spin-Glasses, Physical Review Letters, vol.34, issue.23, p.1754, 1979.
DOI : 10.1103/PhysRevLett.34.1438

A. Crisanti, L. Leuzzi, and G. Parisi, The 3-sat problem with large number of clauses in the ?replica symmetry breaking scheme Circular coloring of random graphs: statistical physics investigation, Journal of Physics A: Mathematical and General Journal of Statistical Mechanics: Theory and Experiment, vol.35, issue.38, pp.481-2016083303, 2002.

G. Parisi, The Marginally Stable Bethe Lattice Spin Glass Revisited, Journal of Statistical Physics, vol.89, issue.3-4, pp.515-542, 2017.
DOI : 10.1103/PhysRevB.89.214202

M. Talagrand, Spin glasses: a challenge for mathematicians: cavity and mean field models, 2003.

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

P. Charbonneau, J. Kurchan, G. Parisi, P. Urbani, and F. Zamponi, Glass and Jamming Transitions: From Exact Results to Finite-Dimensional Descriptions, Annual Review of Condensed Matter Physics, vol.8, issue.1, pp.265-288, 2017.
DOI : 10.1146/annurev-conmatphys-031016-025334
URL : https://hal.archives-ouvertes.fr/cea-01464295