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


© 1999, Society for Industrial and Applied Mathematics
Designed by Donaghy's Web Consulting
Created 11/7/99; Last Updated 11/7/99