On the solution-space geometry of random constraint satisfaction problems, STOC, pp.130-139, 2006. ,
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
Finding a large hidden clique in a random graph, Random Structures and Algorithms, vol.13, pp.3-4457, 1998. ,
Finding a randomly planted assignment in a random 3CN F . manuscript, 2002. ,
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
Survey propagation: an algorithm for satisfiability. Random Structures and Algorithms, pp.201-226, 2005. ,
URL : https://hal.archives-ouvertes.fr/hal-00008893
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
Why Almost All k-Colorable Graphs Are Easy to Color, STACS, pp.121-132, 2007. ,
DOI : 10.1007/s00224-009-9231-5
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
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
Complete Convergence of Message Passing Algorithms for Some Satisfiability Problems, Random, pp.339-350, 2006. ,
DOI : 10.1007/11830924_32
A local search algorithm for 3SAT The Weizmann Institute of Science, 2004. ,
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
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
Some optimal inapproximability results, Journal of the ACM, vol.48, issue.4, pp.798-859, 2001. ,
DOI : 10.1145/502090.502098
Coloring bipartite hypergraphs, Proceedings of the 5th International IPCO Conference on Integer Programming and Combinatorial Optimization, pp.345-358, 1996. ,
Solving random satisfiable 3CN F formulas in expected polynomial time, Proc. 17th ACM-SIAM Symp. on Discrete Algorithms, pp.454-463, 2006. ,
Expected behavior of graph coloring algorithms, Proc. Fundamentals of Computation Theory, pp.447-451, 1977. ,
DOI : 10.1007/3-540-08442-8_114
Average Case Complete Problems, SIAM Journal on Computing, vol.15, issue.1, pp.285-286, 1986. ,
DOI : 10.1137/0215020
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
Pairs of sat assignments and clustering in random boolean formulae, 2005. ,
Local search strategies for satisfiability testing, Proceedings of the Second DIMACS Challange on Cliques, Coloring, and Satisfiability, 1993. ,