Report

Papers

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.