There may be errors, broken links, etc. I will try to fix these in time.

**PPZ**- R. Paturi, P. Pudlak, F. Zane,

Satisfiability Coding Lemma,

Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS 97), 1997. **PPSZ**- R. Paturi, P. Pudlak, M. Saks, and F. Zane.

An improved exponentialtime algorithm for k-SAT,

In Proceedings of the 39th IEEE Conference on Foundations of Computer Science, pages 628-637, 1998. **CIKP**- C. Calabro, R. Impagliazzo, V. Kabanets, and R. Paturi,

The Complexity of Unique k-SAT: An Isolation Lemma for k-CNFs,

Proceedings of the Eighteenth IEEE Conference on Computational Complexity, 2003. **IPZ**- R. Impagliazzo, R. Paturi and F. Zane,

Which Problems have Strongly Exponential Complexity?,

1998 Annual IEEE Symposium on Foundations of Computer Science. **IP**- R. Impagliazzo, R. Paturi,

On the Complexity of k-SAT,

Journal of Computer and System Sciences, volume 62, number 2, pages 367-375, 2001 **AP**-
D. Achlioptas, Y. Peres,

The Threshold for Random k-SAT is 2^k ln2 - O(k),

Proceedings of the 35th Annual ACM Symposium on the Theory of Computation, pages 223-231, 2003.

(the above link is to a new version of the paper) **AS**- N. Alon, J. Spencer,

The Probabilistic Method, 2nd Edition

Wiley-Interscience, 2000 **LW**- N. Linial, A. Wigderson,

Expander Graphs and their Applications,

Lecture notes from a course at Hebrew University, Israel, 2003 **Sch**- U. Schoning,

A Probabilistic Algorithm for k-SAT and Constraint Satisfaction Problems,

Proceedings of the 40th IEEE Symposium on Foundations of Computer Science, pages 410-414, 1999 **SSW**- R. Schuler, U. Schoning, O. Watanabe,

An Improved Randomized Algorithm for 3-SAT,

Technical Report TR-C146, Dept. of Mathematical and Computing Sciences, Tokyo Inst. of Tech., 2001 **Flax**- A. Flaxman

A Spectral Technique for Random Satisfiable 3CNF Formulas,

Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 357-363, 2003 **KPS**- P. Beame, R. Karp, T. Pitassi, M. Saks,

The efficiency of resolution and Davis-Putnam procedures,

Previous version in STOC'98, 1999. **HK**- E. Hirsch, A. Kojevnikov,

UnitWalk: A new SAT solver that uses local search guided by unit clause elimination,

Submitted to a journal, 2002. Preliminary version appeared as PDMI preprint 09/2001. A shorter (but more updated) version of this preprint appears in the electronic proceedings of SAT-2002. Extended astract "Solving Boolean satisfiability using local search guided by unit clause elimination" appeared in Proceedings of CP 2001, LNCS 2239, 605-609, 2001 **AHI**- M. Alekhnovich, E. A. Hirsch, D. Itsykson,

Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas,

Manuscript, last updated February 17, 2004.