The written part of the research exam can be
The power point presentation slides can be found
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.
- R. Paturi, P. Pudlak, F. Zane,
Satisfiability Coding Lemma,
Proceedings of the 38th Annual Symposium on
Foundations of Computer Science (FOCS 97), 1997.
- 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.
- 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.
- R. Impagliazzo, R. Paturi and F. Zane,
Which Problems have Strongly Exponential Complexity?,
1998 Annual IEEE Symposium on Foundations of Computer Science.
- R. Impagliazzo, R. Paturi,
On the Complexity of k-SAT,
Journal of Computer and System Sciences,
volume 62, number 2, pages 367-375, 2001
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)
- N. Alon, J. Spencer,
The Probabilistic Method, 2nd Edition
- N. Linial, A. Wigderson,
Expander Graphs and their Applications,
Lecture notes from a course at Hebrew University, Israel, 2003
- U. Schoning,
A Probabilistic Algorithm for k-SAT and Constraint
Proceedings of the 40th IEEE
Symposium on Foundations of Computer Science,
pages 410-414, 1999
- 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
- 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
- P. Beame, R. Karp, T. Pitassi, M. Saks,
The efficiency of resolution and Davis-Putnam procedures,
Previous version in STOC'98, 1999.
- 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
A shorter (but more updated) version of this preprint
appears in the electronic proceedings of SAT-2002.
"Solving Boolean satisfiability using
local search guided by unit clause elimination"
appeared in Proceedings of CP 2001, LNCS 2239, 605-609, 2001
- 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.