[1]   N. Alon and J. Spencer: The Probabilistic Method. John Wiley and Sons, 2002.

[2]   E. Ben-Sasson and A. Wigderson: Short proofs are narrow— resolution made simple. J. ACM, 48(2):149–169, 2001. [JACM:10.1145/375827.375835].

[3]   V. Chvátal and E. Szemerédi: Many hard examples for resolution. J. ACM, 35(4):759–768, 1988. [JACM:10.1145/48014.48016].

[4]   A. Coja-Oghlan, A. Goerdt, and A. Lanka: Strong refutation heuristics for random k-SAT. Combinatorics, Probability and Computing, 16(1):5–28, 2007. Conference version appeared in Proc. 8th Internat. Workshop on Randomization and Computation (RANDOM ’04), volume 3122 of LNCS, pp. 310–321. Springer, 2004. [doi:10.1017/S096354830600784X, Springer:x1tlgm3cexcj].

[5]   A. Coja-Oghlan, A. Goerdt, A. Lanka, and F. Schadlich: Techniques from combinatorial approximation algorithms yield efficient algorithms for random 2k-sat. Theoretical Computer Science, 329:1–45, 2004. [TCS:10.1016/j.tcs.2004.07.017].

[6]   U. Feige: Relations between average case complexity and approximation complexity. In Proc. 34th STOC, pp. 534–543. ACM Press, 2002. [STOC:509907.509985].

[7]   U. Feige and E. Ofek: Spectral techniques applied to sparse random graphs. Random Structures and Algorithms, 27(2):251–275, 2005. [RSA:10.1002/rsa.20089].

[8]   E. Friedgut and J. Bourgain: Sharp thresholds of graph properties, and the k-sat problem. Journal of the American Mathematical Society, 12(4):1017–1054, 1999. [JAMS:1999-12-04/S0894-0347-99-00305-7].

[9]   J. Friedman, A. Goerdt, and M. Krivelevich: Recognizing more unsatisfiable random 3-sat instances efficiently. SIAM J. on Computing, 35(2):408–430, 2005. [SICOMP:10.1137/S009753970444096X].

[10]   A. Goerdt and M. Krivelevich: Efficient recognition of random unsatisfiable k-SAT instances by spectral methods. In Proc. Ann. Symp. on Theoretical Aspects of Computer Science (STACS ’01), volume 2010 of LNCS, pp. 294–304. Springer, 2001. [STACS:27cr0lrbpr7px7y3].

[11]   A. Goerdt and A. Lanka: Recognizing more random 3-sat instances efficiently. LICS’03 Workshop on Typical Case Complexity and Phase Transitions, 2003.

[12]   M. Hajiaghayi and B. Sorkin: The satisfiability threshold of random 3-SAT is at least 3.52, 2003. [arXiv:math/0310193].

[13]   S. Janson, Y. Stamatiou, and M. Vamvakari: Bounding the unsatisfiability threshold of random 3-sat. Random Structures and Algorithms, 17(2):103–116, 2000. [RSA:10.1002/1098-2418(200009)17:2¡103::AID-RSA2¿3.0.CO;2-P].

[14]   A. Kaporis, L. Kirousis, and E. Lalas: The probabilistic analysis of a greedy satisfiability algorithm. Random Structures and Algorithms, 28(4):444–480, 2006. [RSA:10.1002/rsa.20104].

[15]   S. Khot: Ruling out PTAS for graph min-bisection, densest subgraph and bipartite clique. In Proc. 45th FOCS, pp. 136–145. IEEE Computer Society, 2004. [FOCS:10.1109/FOCS.2004.59].

[16]   U. Zwick: Outward rotations: a tool for rounding solutions of semidefinite programming relaxations, with applications to MAX CUT and other problems. In Proc. 31st STOC, pp. 679–687. ACM Press, 1999. [STOC:301250.301431].