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.

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

R. B. Boppana, Eigenvalues and graph bisection: An average-case analysis (extended abstract), Proc. 28th IEEE Symp. on Found. of Comp. Science, pp.280-285, 1987.
DOI : 10.1109/sfcs.1987.22

A. Braunstein, M. Mezard, M. Weigt, and R. Zecchina, Constraint satisfaction by survey propagation, Computational Complexity and Statistical Physics, 2005.
URL : https://hal.archives-ouvertes.fr/hal-00115530

H. Chen and A. M. Frieze, Coloring bipartite hypergraphs, Integer Programming and Combinatorial Optimization, 5th International IPCO Conference, Proceedings, pp.345-358, 1996.
DOI : 10.1007/3-540-61310-2_26
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.41.3498

U. Feige and J. Kilian, Zero Knowledge and the Chromatic Number, Complexity 96?The Eleventh Annual IEEE Conference on Computational Complexity, pp.187-199, 1998.
DOI : 10.1006/jcss.1998.1587

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, 2006.
DOI : 10.1007/11830924_32

U. Feige and E. Ofek, Finding a Maximum Independent Set in a Sparse Random Graph, SIAM Journal on Discrete Mathematics, vol.22, issue.2, 2006.
DOI : 10.1137/060661090

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

T. G. Gallager, Low-density parity-check codes, IEEE Transactions on Information Theory, vol.8, issue.1, pp.21-28, 1962.
DOI : 10.1109/TIT.1962.1057683

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

M. Luby, M. Mitzenmacher, and M. A. Shokrollahi, Analysis of Random Processes via And-Or Trees, Proc. 9th Symp. on Discrete Algorithms, 1998.

M. Luby, M. Mitzenmacher, M. A. Shokrollahi, and D. Spielman, Analysis of low density parity check codes and improved designs using irregular graphs, Proceedings of the 30th ACM Symposium on Theory of Computing, pp.249-258, 1998.

M. Luby, M. Mitzenmacher, M. A. Shokrollahi, and D. Spielman, Efficient erasure correcting codes, IEEE Transactions on Information Theory, vol.47, issue.2, pp.569-584, 2001.
DOI : 10.1109/18.910575

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

T. Richardson, A. Shokrollahi, and R. Urbanke, Design of capacity-approaching irregular low-density parity-check codes, IEEE Transactions on Information Theory, vol.47, issue.2, pp.619-637, 2001.
DOI : 10.1109/18.910578

J. Pearl, Probabilistic reasoning in intelligent systems: networks of plausible inference, 1988.

M. Sipser and D. A. Spielman, Expander codes, IEEE Transactions on Information Theory, vol.42, issue.6, pp.1710-1722, 1996.
DOI : 10.1109/18.556667