D. Achlioptas and F. Ricci-tersenghi, On the solution-space geometry of random constraint satisfaction problems, STOC, pp.130-139, 2006.

N. Alon and N. Kahale, 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, M. Krivelevich, and B. Sudakov, Finding a large hidden clique in a random graph, Random Structures and Algorithms, vol.13, pp.3-4457, 1998.

E. Ben-sasson, Y. Bilu, and D. Gutfreund, Finding a randomly planted assignment in a random 3CN F . manuscript, 2002.

A. Blum and J. Spencer, Coloring Random and Semi-Random k-Colorable Graphs, Journal of Algorithms, vol.19, issue.2, pp.204-234, 1995.
DOI : 10.1006/jagm.1995.1034

A. Braunstein, M. Mezard, and R. Zecchina, Survey propagation: an algorithm for satisfiability. Random Structures and Algorithms, pp.201-226, 2005.
URL : https://hal.archives-ouvertes.fr/hal-00008893

H. Chen, An Algorithm for SAT Above the Threshold, 6th International Conference on Theory and Applications of Satisfiability Testing, pp.14-24, 2003.
DOI : 10.1007/978-3-540-24605-3_2

A. Coja-oghlan, M. Krivelevich, and D. Vilenchik, Why Almost All k-Colorable Graphs Are Easy to Color, STACS, pp.121-132, 2007.
DOI : 10.1007/s00224-009-9231-5

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

U. Feige and R. Krauthgamer, Finding and certifying a large hidden clique in a semirandom graph, Random Structures and Algorithms, vol.25, issue.2, pp.195-208, 2000.
DOI : 10.1002/(SICI)1098-2418(200003)16:2<195::AID-RSA5>3.0.CO;2-A

U. Feige, E. Mossel, and D. Vilenchik, Complete Convergence of Message Passing Algorithms for Some Satisfiability Problems, Random, pp.339-350, 2006.
DOI : 10.1007/11830924_32

U. Feige and D. Vilenchik, A local search algorithm for 3SAT The Weizmann Institute of Science, 2004.

A. Flaxman, A spectral technique for random satisfiable 3CNF formulas, Proc. 14th ACM-SIAM Symp. on Discrete Algorithms, pp.357-363, 2003.
DOI : 10.1002/rsa.20213

E. Friedgut, Sharp thresholds of graph properties, and the k-sat problem, Journal of the American Mathematical Society, vol.12, issue.04, pp.1017-1054, 1999.
DOI : 10.1090/S0894-0347-99-00305-7

J. Håstad, Some optimal inapproximability results, Journal of the ACM, vol.48, issue.4, pp.798-859, 2001.
DOI : 10.1145/502090.502098

C. Hui and A. M. Frieze, Coloring bipartite hypergraphs, Proceedings of the 5th International IPCO Conference on Integer Programming and Combinatorial Optimization, pp.345-358, 1996.

M. Krivelevich and D. Vilenchik, Solving random satisfiable 3CN F formulas in expected polynomial time, Proc. 17th ACM-SIAM Symp. on Discrete Algorithms, pp.454-463, 2006.

L. Ku?era, Expected behavior of graph coloring algorithms, Proc. Fundamentals of Computation Theory, pp.447-451, 1977.
DOI : 10.1007/3-540-08442-8_114

L. Levin, Average Case Complete Problems, SIAM Journal on Computing, vol.15, issue.1, pp.285-286, 1986.
DOI : 10.1137/0215020

M. Mezard, T. Mora, and R. Zecchina, Clustering of Solutions in the Random Satisfiability Problem, Physical Review Letters, vol.94, issue.19, pp.197-205, 2005.
DOI : 10.1103/PhysRevLett.94.197205

URL : https://hal.archives-ouvertes.fr/hal-00004732

T. Mora, M. Mezard, and R. Zecchina, Pairs of sat assignments and clustering in random boolean formulae, 2005.

B. Selman, H. A. Kautz, and B. Cohen, Local search strategies for satisfiability testing, Proceedings of the Second DIMACS Challange on Cliques, Coloring, and Satisfiability, 1993.