Report

The written part of the research exam can be obtained here. The power point presentation slides can be found here

Papers

The following lists the papers I have already read or am considering reading in preparation for the research exam. The common theme is upper bounds for k-SAT.

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.