[1]   Dimitris Achlioptas and Amin Coja-Oghlan: Algorithmic barriers from phase transitions. In Proc. 49th FOCS, pp. 793–802. IEEE Comp. Soc. Press, 2008. [doi:10.1109/FOCS.2008.11]

[2]   Dimitris Achlioptas, Amin Coja-Oghlan, and Federico Ricci-Tersenghi: On the solution-space geometry of random constraint satisfaction problems. Random Structures & Algorithms, 38(3):251–268, 2011. Preliminary version in STOC’06. [doi:10.1002/rsa.20323]

[3]   Mikhail Alekhnovich and Eli Ben-Sasson: Linear upper bounds for random walk on small density random 3-CNFs. SIAM J. Comput., 36(5):1248–1263, 2007. Preliminary version in FOCS’03. [doi:10.1137/S0097539704440107]

[4]   Noga Alon and Nabil Kahale: A spectral technique for coloring random 3-colorable graphs. SIAM J. Comput., 26(6):1733–1748, 1997. Prelimiary version in STOC’94. [doi:10.1137/S0097539794270248]

[5]   Noga Alon, Michael Krivelevich, and Benny Sudakov: Finding a large hidden clique in a random graph. Random Structures & Algorithms, 13(3-4):457–466, 1998. Preliminary version in SODA’98. [doi:10.1002/(SICI)1098-2418(199810/12)13:3/4¡457::AID-RSA14¿3.0.CO;2-W]

[6]   Noga Alon and Joel Spencer: The Probabilistic Method. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley, 2nd edition, 2000.

[7]   Alfredo Braunstein, Marc Mézard, and Riccardo Zecchina: Survey propagation: An algorithm for satisfiability. Random Structures & Algorithms, 27(2):201–226, 2005. [doi:10.1002/rsa.20057]

[8]   Andrei Z. Broder, Alan M. Frieze, and Eli Upfal: On the satisfiability and maximum satisfiability of random 3-CNF formulas. In Proc. 4th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’93), pp. 322–330. ACM Press, 1993. [ACM:313559.313794]

[9]   Hui Chen and Alan M. Frieze: Coloring bipartite hypergraphs. In Proc. 5th Ann. Conf. on Integer Programming and Combinatorial Optimization (IPCO ’96), pp. 345–358, London, UK, 1996. Springer. [doi:10.1007/3-540-61310-2_26]

[10]   Amin Coja-Oghlan: A better algorithm for random k-SAT. SIAM J. Comput., 39(7):2823–2864, 2010. Preliminary version in ICALP’09. [doi:10.1137/09076516X]

[11]   Amin Coja-Oghlan, Michael Krivelevich, and Dan Vilenchik: Why almost all k-CNF formulas are easy. In Proc. 13th Internat. Conf. on Analysis of Algorithms (AofA’07), pp. 89–102. DMTCS, 2007. DMTCS.

[12]   Amin Coja-Oghlan and Angelica Y. Pachon-Pinzon: The decimation process in random k-SAT. SIAM J. Discrete Math., 26(4):1471–1509, 2012. Preliminary versions in ICALP’11 and SODA’11. [doi:10.1137/110842867]

[13]   Stephen A. Cook: The complexity of theorem-proving procedures. In Proc. 3rd STOC, pp. 151–158. ACM Press, 1971. [doi:10.1145/800157.805047]

[14]   James M. Crawford and Larry D. Auton: Experimental results on the crossover point in random 3-SAT. Artif. Intell., 81(1-2):31–57, 1996. Preliminary version in AAAI’93. [doi:10.1016/0004-3702(95)00046-1]

[15]   Olivier Dubois, Yacine Boufkhad, and Jacques Mandler: Typical random 3-SAT formulae and the satisfiability threshold. In Proc. 11th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’00), pp. 126–127. ACM Press, 2000. [ACM:338243]

[16]   Uriel Feige, Elchanan Mossel, and Dan Vilenchik: Complete convergence of message passing algorithms for some satisfiability problems. In Proc. 10th Internat. Workshop on Randomization and Computation (RANDOM’06), pp. 339–350. Springer, 2006. [doi:10.1007/11830924_32]

[17]   Uriel Feige and Dan Vilenchik: A local search algorithm for 3SAT. Technical report, The Weizmann Institute of Science, 2004. Available at author’s home page.

[18]   Abraham Flaxman: A spectral technique for random satisfiable 3CNF formulas. Random Structures & Algorithms, 32(4):519–534, 2008. Preliminary version in SODA’03. [doi:10.1002/rsa.20213]

[19]   Ehud Friedgut: Sharp thresholds of graph properties, and the k-SAT problem. J. Amer. Math. Soc., 12(4):1017–1054, 1999. [doi:10.1090/S0894-0347-99-00305-7]

[20]   Wassily Hoeffding: Probability inequalities for sums of bounded random variables. J. Amer. Stat. Assoc., 58(301):13–30, 1963. JSTOR.

[21]   Alexis C. Kaporis, Lefteris M. Kirousis, and Efthimios G. Lalas: The probabilistic analysis of a greedy satisfiability algorithm. Random Structures & Algorithms, 28(4):444–480, 2006. Preliminary version in ESA’02. [doi:10.1002/rsa.20104]

[22]   Elias Koutsoupias and Christos H. Papadimitriou: On the greedy algorithm for satisfiability. Inform. Process. Lett., 43(1):53–55, 1992. [doi:10.1016/0020-0190(92)90029-U]

[23]   Michael Krivelevich and Dan Vilenchik: Solving random satisfiable 3CNF formulas in expected polynomial time. In Proc. 17th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’06), pp. 454–463. ACM Press, 2006. [doi:10.1145/1109557.1109608]

[24]   Michael Luby, Michael Mitzenmacher, Amin Shokrollahi, and Daniel A. Spielman: Efficient erasure correcting codes. IEEE Trans. Inform. Theory, 47(2):569–584, 2001. [doi:10.1109/18.910575]

[25]   Michael Luby, Michael Mitzenmacher, Amin Shokrollahi, and Daniel A. Spielman: Improved low-density parity-check codes using irregular graphs. IEEE Trans. Inform. Theory, 47(2):585–598, 2001. Preliminary versions in ISIT’98 and STOC’98. [doi:10.1109/18.910576]

[26]   Judea Pearl: Reverend Bayes on inference engines: A distributed hierarchical approach. In Proc. 2nd Nat. Conf. on Artificial Intelligence (AAAI’82), pp. 133–136, 1982. AAAI.

[27]   Thomas J. Richardson, Amin Shokrollahi, and Rüdiger L. Urbanke: Design of capacity-approaching irregular low-density parity-check codes. IEEE Trans. Inform. Theory, 47(2):619–637, 2001. [doi:10.1109/18.910578]