Sunday, January 9

Session 3B

1:30 PM-3:35 PM
Room: Oregon/Nevada

1:30 Typical Random 3-SAT Formulae and the Satisfiability Threshold

Olivier Dubois, CNRS-Université Paris 6, France; Yacine Boufkhad, Université d' Artois, France; and Jacques Mandler, CNRS-Université Paris 6, France

1:55 A Lower Bound for DLL Algorithms for k-SAT

Pavel Pudlak and Russell Impagliazzo, University of California, San Diego

2:20 On Permutations with Limited Independence

Toshiya Itoh and Yoshinori Takei, Tokyo Institute of Technology, Japan; and Jun Tarui, University of Electro-Communications, Japan

2:45 Min-Wise versus Linear Independence

Andrei Z. Broder, Compaq Systems Research Center; and Uriel Feige, Weizmann Institute, Israel

3:10 Hamiltonicity and Colorings of Arrangement Graphs

Stefan Felsner, Freie Universität Berlin, Germany; Ferran Hurtado and Marc Noy, Universitat Politecnica de Catalunya, Spain; and Ileana Streinu, Smith College