[1] D. Achlioptas, P. Beame, and M. Molloy, Exponential bounds for DPLL below the satisfiability
threshold, in Proceedings of the Fifteenth Annual ACM-SIAM Symposium on
Discrete Algorithms (SODA), 2004, pp. 132–133.
[2] D. Achlioptas and A. Coja-Oghlan, Algorithmic barriers from phase transitions, in Proceedings
of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS),
2008, pp. 793–802.
[3] D. Achlioptas and C. Moore, Random k-SAT: Two moments suffice to cross a sharp threshold,
SIAM J. Comput., 36 (2006), pp. 740–762.
[4] D. Achlioptas and Y. Peres, The threshold for random k-SAT is 2k log 2
−
O(k), J. Amer.
Math. Soc., 17 (2004), pp. 947–973.
[5] J. Ardelius and L. Zdeborova, Exhaustive enumeration unveils clustering and freezing in
random 3-satisfiability problem, Phys. Rev. E, 78 (2008), 040101(R).
[6] A. Braunstein, M. M´ ezard, and R. Zecchina, Survey propagation: An algorithm for satisfiability,
Random Structures Algorithms, 27 (2005), pp. 201–226.
[7] M.-T. Chao and J. Franco, Probabilistic analysis of a generalization of the unit-clause literal
selection heuristic for the k-satisfiability problem, Inform. Sci., 51 (1990), pp. 289–314.
[8] V. Chv´ atal and B. Reed, Mick gets some (the odds are on his side), in Proceedings of the
33rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), 1992, pp.
620–627.
[9] A. Coja-Oghlan, U. Feige, A. Frieze, M. Krivelevich, and D. Vilenchik, On smoothed
k-CNF formulas and the Walksat algorithm, in Proceedings of the Twentieth Annual ACM-
SIAM Symposium on Discrete Algorithms (SODA), 2009, pp. 451–460.
[10] M. Davis, G. Longemann, and D. Loveland, A machine program for theorem proving, Comm.
ACM, 5 (1962), pp. 394–397.
[11] O. Dubois, Y. Boufkhad, and J. Mandler, Typical random 3-SAT formulae and the satisfiability
threshold, in Proceedings of the Eleventh Annual ACM-SIAM Symposium on
Discrete Algorithms (SODA), 2000, pp. 126–127.
[12] R. Durrett, Probability and Examples, 3rd ed., Thomson/Brooks/Cole, Belmont, CA, 2005.
[13] A. Flaxman, Algorithms for random 3-SAT, in Encyclopedia of Algorithms, M.-Y. Kao, ed.,
Springer-Verlag, Heidelberg, 2008, pp. 742–744.
[14] E. Friedgut, Sharp thresholds of graph properties, and the k-SAT problem, J. Amer. Math.
Sci., 12 (1999), pp. 1017–1054.
[15] A. Frieze and S. Suen, Analysis of two simple heuristics on a random instance of k-SAT, J.
Algorithms, 20 (1996), pp. 312–355.
[16] E. Goldberg and Y. Novikov, BerkMin: A fast and robust SAT-solver, Discrete Appl. Math.,
155 (2007), pp. 1549–1561.
[17] M. Hajiaghayi and G. Sorkin, The Satisfiability Threshold of Random 3-SAT Is at Least
3.52, Research report RC22942, IBM, T. J. Watson Research Center, Yorktown Heights,
NY, 2003.
[18] S. Janson, T. � Luczak, and A. Ruci´ nski, Random Graphs, Wiley-Interscience, New York,
2000.
[19] A. Kaporis, L. Kirousis, and E. Lalas, The probabilistic analysis of a greedy satisfiability
algorithm, Random Structures Algorithms, 28 (2006), pp. 444–480.
[20] J. H. Kim, Poisson Cloning Model for Random Graphs, preprint, 2008; available online from
http://www.arxiv.org/abs/0805.4133v1.
[21] E. Maneva, E. Mossel, and M. J. Wainwright, A new look at survey propagation and its
generalizations, J. ACM, 54 (2007), article 17.
[22] A. Montanari, F. Ricci-Tersenghi, and G. Semerjian, Solving constraint satisfaction problems
through belief propagation-guided decimation, in Proceedings of the 45th Annual
Allerton Conference on Communication, Control, and Computing, University of Illinois
at Urbana-Champaign, Urbana, IL, 2007.
[23] G. Semerjian and R. Monasson, A study of pure random walk on random satisfiability problems
with “physical” methods, in Proceedings of the 6th International Conference on Theory
and Applications of Satisfiability Testing (SAT), Springer-Verlag, Berlin, 2003, pp.
120–134.