DIMACS Workshop on Faster Exact Solutions for NP-Hard Problems

Program

8:45: REGISTRATION
9:10-9:40: Finding the closest lattice vector when it's unusually close --- Philip Klein, Brown University
9:45-10:15: An Exact Algorithm for 3-Coloring --- David Eppstein, University of California, Irvine
10:20-10:35: BREAK
10:40-11:10: Maximum Independent Set Algorithms: Improved Analysis --- Mike Robson, Universite de Bordeaux
11:15-11:45: Robust Algorithms for the Stable Set Problem --- Vadim Lozin, Rutgers University
11:50-12:20: Applying structions to the independent set problem --- Richard Beigel, DIMACS and University of Illinois
12:25-2:25: LUNCH BREAK
2:30-3:00: Algorithms for k-SAT based on Covering Codes --- Edward Hirsch, Steklov Institute of Mathematics at St. Petersburg
3:05-3:35: Faster Exact Solutions for Max2SAT --- Jens Gramm, University of Tuebingen
3:40-4:10: Using poly-time SAT decidable and recognisable hierarchies of conjunctive normal forms for improved SAT decision and general lower bounds on resolution with oracles --- Oliver Kullman, University of Toronto
4:15-4:35: BREAK
4:40-5:10: Improved Exponential Time Algorithms for Vertex Cover --- Jianer Chen, Texas A&M University
5:15-5:45: On Efficient Fixed Parameter Algorithms for Weighted Vertex Cover --- Rolf Niedermeier, University of Tuebingen

9:00: REGISTRATION
9:30-10:30: Satisfiability Testing: Theory and Practice (Invited Talk) --- Bart Selman, Cornell University
10:35-10:55: BREAK
11:00-11:30: Exponential Algorithms for SAT and MAJSAT --- Michael Littman, AT&T Labs Research and Duke University
11:35-12:05: Complexity of k-SAT --- Ramamohan Paturi, University of California, San Diego