Saturday, January 6, 2001

Sunday, January 7, 2001

Sessions 1A | 1B | 1C | 2-Invited |
3A | 3B | 3C | 4A | 4B | 4C

Monday, January 8, 2001

Sessions 5A | 5B | 5C | 6-Invited |
7A | 7B | 7C | 8A | 8B | 8C

Tuesday, January 9, 2001

Sessions 9A | 9B | 9C | 10-Invited |
11A | 11B | 11C | 12A | 12B | 12C

DA01 Home

Time Allowed for Each Presentation

The conference organizers expect every speaker of a scheduled presentation to register and attend the conference. If it becomes necessary for a speaker to cancel the presentation, the speaker is expected to find an alternate presenter immediately, preferably one of the speaker's co-authors. The speaker must inform the SIAM Conference Department immediately of any change to his/her scheduled presentation.

A "no-show" or canceled presentation can cause serious inconvenience to the attendees and conference organizers.

Session 1A
9:00 AM Combinatorial Approximation Algorithms for the Maximum Directed Cut Problem

Eran Halperin and Uri Zwick, Tel Aviv University, Israel

9:25 AM Approximation Algorithms for the 0-Extension Problem

Gruia Calinescu, Illinois Institute of Technology; Howard Karloff, AT&T Labs-Research and Georgia Institute of Technology; and Yuval Rabani, Technion-IIT, Israel

9:50 AM A Faster Implementation of the Goemans-Williamson Clustering Algorithm

Richard Cole, New York University; Ramesh Hariharan, Indian Institute of Science, India; Moshe Lewenstein, Bar-Ilan University and New York University; and Ely Porat, Bar-Ilan University, Israel

10:15 AM Tree Packing and Approximating k-Cuts

Joseph (Seffi) Naor and Yuval Rabani, Technion, Israel

Session 1B
9:00 AM Generating Well-Shaped Delaunay Meshes in 3D

Xiang-Yang Li, University of Illinois at Urbana-Champaign and Illinois Institute of Technology; and Shang-Hua Teng, University of Illinois at Urbana-Champaign and Akamai Technologies

9:25 AM Approximation Algorithms for TSP with Neighborhoods in the Plane

Adrian Dumitrescu, Joseph S.B. Mitchell, University at Stony Brook

9:50 AM Dynamic Skin Triangulation

Ho-Lun Cheng, University of Illinois at Urbana-Champaign; Tamal K. Dey, Ohio State University; Herbert Edelsbrunner, Duke University; and John Sullivan, University of Illinois at Urbana-Champaign

10:15 AM Online Point Location in Planar Arrangements and Its Applications

Sariel Har-Peled, University of Illinois, Urbana; and Micha Sharir, Tel Aviv University, Israel

Session 1C
9:00 AM Reconciling Simplicity and Realism in Parallel Disk Models

Peter Sanders, Max Planc Institut für Informatick Saarbrücken, Germany

9:25 AM Distribution Sort With Randomized Cycling

Jeffrey Scott Vitter and David A. Hutchinson, Duke University

9:50 AM External Memory BFS on Undirected Graphs with Bounded Degree

Ulrich Meyer, Max-Planck-Institut für Informatik, Germany

10:15 AM I/O-Efficient Algorithms for Graphs of Bounded Treewidth

Anil Maheshwari and Norbert Zeh, Carleton University, Ottawa, Canada

Session 2 -
Invited Presentation - Serving Billions of Pages to Hundreds of Millions of People is Harder Than It Seems

Yahoo! served an average of 780 million page views a day to more than 166 million unique users during September 2000. These numbers have been growing at an exponential rate for several years and are expected to continue to do so. This talk will highlight some of the non-obvious problems that we need to solve to meet this challenge.

Udi Manber, Yahoo, USA

1:30 PM � 3:35 PM Concurrent Sessions

Session 3A
1:30 PM Constructing Worst Case Instances for Semidefinite Programming Based Approximation Algorithms

Noga Alon, Tel Aviv University, Israel; Benny Sudakov, Princeton University and Institute for Advanced Study; and Uri Zwick, Tel Aviv University, Israel

1:55 PM Randomized Combinatorial Algorithms for Linear Programming when the Dimension is Moderately High

M. Pellegrini, Istituto di Matematica Computazionale del CNR, Italy

2:20 PM Approximation Algorithms for the Metric Labeling Problem via a New Linear Programming Formulation

Chandra Chekuri, Bell Labs; Sanjeev Khanna, University of Pennsylvania; Joseph (Seffi) Naor, Technion, Israel; and Leonid Zosin, ITG Inc.

2:45 PM Lattice Approximation and Linear Discrepancy of Totally Unimodular Matrices

Benjamin Doerr, Christian-Albrechts-Universität zu Kiel, Germany

3:10 PM On Polynomial Approximations to the Shortest Lattice Vector Length

Ravi Kumar and D. Sivakumar, IBM Almaden Research Center

Session 3B
1:30 PM Approximation for Minimum Triangulation of Convex Polyhedra

F.Y.L. Chin, Hong Kong University, Hong Kong; S.P.Y. Fung, Hong Kong University, Hong Kong; and C.A. Wang, Memorial University NFLD, Canada

1:55 PM Optimal Covering Tours with Turn Costs

Ester M. Arkin, Michael A. Bender, SUNY Stony Brook; Erik D. Demaine, University of Waterloo, Canada; Sandor P. Fekete, Fachbereich Mathematik TU Berlin, Germany; Joseph S.B. Mitchell, Saurabh Sethia, SUNY Stony Brook

2:20 PM Maintaining Approximate Extent of Moving Points

Pankaj K. Agarwal, Duke University; and Sariel Har-Peled, University of Illinois, Urbana

2:45 PM Simplified Kinetic Connectivity for Rectangles and Hypercubes

John Hershberger, Mentor Graphics Corporation; and Subhash Suri, University of California, Santa Barbara

3:10 PM Static and Kinetic Geometric Spanners with Applications

Menelaos I. Karavelas and Leonidas J. Guibas, Stanford University

Session 3C
1:30 PM Gossip is Synteny: Incomplete Gossip and an Exact Algorithm for Syntenic Distance

David Liben-Nowell, MIT

1:55 PM Absolute Convergence: True Trees from Short Sequences

Tandy Warnow, University of Texas at Austin; Bernard M.E. Moret, University of New Mexico; Katherine St. John, City University of New York

2:20 PM Performance Study of Phylogenetic Methods: (Unweighted) Quartet Methods and Neighbor-Joining

Katherine St. John, City University of New York; Tandy Warnow, University of Texas at Austin; Bernard M.E. Moret, University of New Mexico; and Lisa Vawter, SmithKline Beecham

2:45 PM A Probabilistic Analysis of a Greedy Algorithm Arising from Computational Biology

Daniel G. Brown, University of Waterloo, Canada

3:10 PM On the Midpath Tree Conjecture: A Counter-Example

Rahul Shah, Rutgers University; and Martin Farach-Colton, Google Inc.

Session 4A
4:00 PM Distance Labeling in Graphs

Cyril Gavoille, Université Bordeaux, France; David Peleg, The Weizmann Institute of Science, Israel; Stéphane Pérennes, Université de Nice-Sophia Antipolis, France; and Ran Raz, The Weizmann Institute of Science, Israel

4:25 PM Steiner Points in Tree Metrics Don't (Really) Help

Anupam Gupta, University of California, Berkeley

4:50 PM Fast Approximation of Centrality

David Eppstein and Joseph Wang, University of California, Irvine

5:15 PM K-Pair Delay Constrained Minimum Cost Routing in Undirected Networks

Guangting Chen, Hangzhou Institute of Electronic Engineering, Hangzhou, P.R. China; and Guoliang Xue, University of Vermont

5:40 PM A Deterministic Algorithm for the COST-DISTANCE Problem

Chandra Chekuri, Bell Labs; Sanjeev Khanna, University of Pennsylvania; and Joseph (Seffi) Naor, Technion, Israel

Session 4B
4:00 PM Shape Sensitive Geometric Permutations

Yunhong Zhou, Washington University, St. Louis; and Subhash Suri, University of California, Santa Barbara

4:25 PM Geometric Permutations of High Dimensional Spheres

Yingping Huang, University of Notre Dame; Jinhui Xu, State University of New York at Buffalo; and Danny Z. Chen, University of Notre Dame

4:50 PM Inserting an Edge into a Planar Graph

Carsten Gutwenger, Max-Planck-Institut für Informatic, Germany; Petra Mutzel and René Weiskircher, Technische Universität Wien, Austria

5:15 PM Entropy-Preserving Cuttings and Space-Efficient Planar Point Location

Sunil Arya, Theocharis Malamatos, The Hong Kong University of Science and Technology, Hong Kong; and David M. Mount, University of Maryland, College Park

5:40 PM A Simple Entropy-Based Algorithm for Planar Point Location

Sunil Arya, Theocharis Malamatos, The Hong Kong University of Science and Technology, Hong Kong; and David M. Mount, University of Maryland, College Park

Session 4C
4:00 PM An Experimental Study of an Opportunistic Index

Paolo Ferragina, Università di Pisa, Italy; and Giovanni Manzini, Università del Piemonte Orientale, Alessandria, Italy

4:25 PM Overlap Matching

Amihood Amir, Bar-Ilan University, Israel; Richard Cole, New York University; Ramesh Hariharan, Indian Institute of Science, India; Moshe Lewenstein and Ely Porat, Bar-Ilan University, Israel

4:50 PM A Linear Lower Bound on Index Size for Text Retrieval

Erik D. Demaine, University of Waterloo, Canada; and Alejandro López-Ortiz, University of New Brunswick, Canada

5:15 PM Pattern Matching for Sets of Segments

Alon Efrat, Piotr Indyk, Stanford University; and Suresh Venkatasubramanian, AT&T Labs - Research

5:40 PM Approximate Subset Matching with Don't Cares

Amihood Amir, Moshe Lewenstein and Ely Porat, Bar-Ilan University, Israel

6:05 PM Dynamic String Searching

Arne Andersson, Uppsala University, Sweden; and Mikkel Thorup, AT& T Labs-Research

Session 5A
9:00 AM On Approximating the Achromatic Number

Guy Kortsarz, Open University of Israel; and Robert Krauthgamer, Weizmann Institute of Science, Israel

9:25 AM Coloring k-colorable Graphs using Smaller Palettes

Eran Halperin, Ram Nathaniel and Uri Zwick, Tel Aviv University, Israel

9:50 AM Approximating Coloring and Maximum Independent Sets in 3-uniform Hypergraphs

Michael Krivelevich, Ram Nathaniel, Tel Aviv University, Israel, and Benny Sudakov, Princeton University

10:15 AM Improved Algorithms for 3-Coloring, 3-Edge-Coloring, and Constraint Satisfaction

David Eppstein, University of California, Irvine

Session 5B
9:00 AM Computing Optimal ±-fat and ±-small Decompositions

Mirela Damian-Iordache and Sriram V. Pemmaraju, University of Iowa

9:25 AM Optimal Planar Point Location

John Iacono, Rutgers University, New Brunswick

9:50 AM Polygonal Path Approximation with Angle Constraints

Danny Z. Chen, University of Notre Dame; Ovidiu Daescu, University of Texas at Dallas; John Hershberger, Mentor Graphics; Peter M. Kogge, University of Notre Dame; and Jack Snoeyink, University of North Carolina at Chapel Hill

10:15 AM Reconstructing a Collection of Curves with Corners and Endpoints

Stefan Funke and Edgar A. Ramos, Max-Planck-Institut für Informatic, Germany

Session 5C
9:00 AM Web Caching using Access Statistics

Adam Meyerson, Kamesh Munagala, and Serge Plotkin, Stanford University

9:25 AM Competitive On-Line Stream Merging Algorithms for Media-on-Demand

Amotz Bar-Noy, AT&T Labs - Research; and Richard E. Ladner, University of Washington, Seattle

9:50 AM On-line Restricted Caching

Mark Brehob, Richard Enbody, Eric Torng and Stephen Wagner, Michigan State University

10:15 AM Approximate Majorization and Fair Online Load Balancing

Ashish Goel, University of Southern California, Los Angeles; Adam Meyerson and Serge Plotkin, Stanford University

12:00 PM � 1:30 PM

Session 7A
1:30 PM Learning Markov Networks: Maximum Bounded Tree-Width Graphs

David Karger and Nathan Srebro, MIT

1:55 PM Approximately Covering by Cycles in Planar Graphs

Dieter Rautenbach and Bruce Reed, Université Paris, France

2:20 PM Practical Approximation Algorithms for Zero- and Bounded-Skew Trees

Alexander Z. Zelikovsky, Georgia State University; and Ion I. M
ndoiu, Georgia Institute of Technology

2:45 PM Approximating the Minimum Strongly Connected Subgraph via a Matching Lower Bound

Adrian Vetta, MIT

3:10 PM Improved Approximation Algorithms for Rectangle Tiling and Packing

Piotr Berman, Pennsylvania State University; Bhaskar DasGupta, Rutgers University, Camden; S. Muthukrishnan, AT& T Labs - Research; and Suneeta Ramaswami, Rutgers University, Camden

Session 7B
1:30 PM Secure Notarization of Paper Text Documents

Matthias Ruhl, MIT; Marshall Bern and David Goldberg, Xerox PARC

1:55 PM Sublinear Time Approximate Clustering

Nina Mishra, Hewlett-Packard Labs; Dan Oblinger, IBM TJ Watson Labs; and Leonard Pitt, University of Illinois at Urbana-Champaign

2:20 PM Efficient Oblivious Transfer Protocols

Moni Naor, Weizmann Institute of Science, Israel; and Benny Pinkas, Intertrust Technologies

2:45 PM Constructing Pseudo-Random Permutations with a Prescribed Structure

Moni Naor, Weizmann Institute of Science, Israel; and Omer Reingold, AT&T Labs � Research

3:10 PM Robust Algorithms for Restricted Domains

Vijay Raghavan and Jeremy Spinrad, Vanderbilt University

Session 7C
1:30 PM Polynomial Algorithms for Partitioning Problems on Graphs with Fixed Clique-width

Daniel Kobler, Fields Institute for Research in Mathematical Sciences, Canada; and Udi Rotics, University of Toronto, Canada

1:55 PM A Polynomial Time Recognition Algorithm for Probe Interval Graphs

Julie L. Johnson and Jeremy P. Spinrad, Vanderbilt University

2:20 PM Colored Tutte Polynomials and Kauffman Brackets for Graphs of Bounded Tree Width

J.A. Makowsky, Technion-Israel Institute of Technology, Israel

2:45 PM A New Constructive Root Bound for Algebraic Expressions

Chen Li and Chee Yap, New York University

3:10 PM Orderly Spanning Trees with Applications to Graph Encoding and Graph Drawing

Yi-Ting Chiang, Ching-Chi Lin and Hsueh-I Lu, Institute of Information Science, Academia Sinica, Taiwan

3:35 PM � 4:00 PM

Session 8A
4:00 PM Alternatives to Splay Trees with O(log n) Worst-case Access Times

John Iacono, Rutgers University, New Brunswick

4:25 PM Worst Case Constant Time Priority Queue

Andrej Brodnik, Institute of Mathematics, Physics, and Mechanics, Ljubljana, Slovenia and Luleå University of Technology, Sweden; Svante Carlsson, Luleå University of Technology, Sweden; Johan Karlsson, Luleå University of Technology, Sweden; and J. Ian Munro, University of Waterloo, Canada

4:50 PM Representing Dynamic Binary Trees Succinctly

J. Ian Munro, University of Waterloo, Canada; Venkatesh Raman, Institute of Mathematical Sciences, Chennai, India; and Adam J. Storm, University of Waterloo, Canada

5:15 PM Making Data Structures Confluently Persistent

Amos Fiat and Haim Kaplan, Tel Aviv University, Israel

5:40 PM Compact Labeling Schemes for Ancestor Queries

Serge Abiteboul, INRIA-Rocquencourt, France; Haim Kaplan and Tova Milo, Tel Aviv University, Israel

Session 8B
4:00 PM Better Approximation Algorithms for Bin Covering

Janos Csirik, University of Szeged, Hungary; David S. Johnson, AT& T Labs; and Claire Kenyon, Université Paris-Sud, France

4:25 PM New Approaches to Covering and Packing Problems

Aravind Srinivasan, Bell Laboratories, Lucent Technologies

4:50 PM Parallel Processor Scheduling with Delay Constraints

Daniel W. Engels, Jon Feldman, David R. Karger and Matthias Ruhl, MIT

5:15 PM Approximation Algorithms for Extensible Bin Packing

E.G. Coffman, Jr., Columbia University; and George S. Lueker, University of California, Irvine

5:40 PM Scheduling Precedence-Constrained Jobs with Stochastic Processing Times on Parallel Machines

Martin Skutella and Marc Uetz, Technische Universität Berlin, Germany

Session 8C
4:00 PM Loss-Bounded Analysis for Differentiated Services

Alexander Kesselman, Check Point Software Technologies and Tel Aviv University, Israel; and Yishay Mansour, Tel Aviv University, Israel

4:25 PM Stability Preserving Transformations: Packet Routing Networks with Edge Capacities and Speeds

Allan Borodin, University of Toronto, Canada; Rafail Ostrovsky, Telcordia Technologies; and Yuval Rabani, IIT, Israel

4:50 PM Distributed Admission Control, Scheduling, and Routing with Stale Information

Ashish Goel, University of Southern California, Los Angeles; Adam Meyerson and Serge Plotkin, Stanford University

5:15 PM On Algorithms for Efficient Data Migration

Joseph Hall, Jason Hartline, Anna R. Karlin, Jared Saia, University of Washington, Seattle; and John Wilkes, Hewlett-Packard Research Laboratories

5:40 PM Fast Distributed Graph Coloring with O(”) Colors

Gianluca De Marco, Università di Salerno, Italy and Andrzej Pelc, Université du Québec a Hull, Canada

SIAM Business Meeting

Session 9A
9:00 AM Improved Algorithms for Fault Tolerant Facility Location

Sudipto Guha, AT&T Shannon Labs; Adam Meyerson and Kamesh Munagala, Stanford University

9:25 AM Algorithms for Facility Location Problems with Outliers

Moses Charikar, Stanford University; Samir Khuller, David M. Mount, University of Maryland, College Park; and Giri Narasimhan, University of Memphis

9:50 AM The Probabilistic Relationship between the Assignment and Asymmetric Traveling Salesman Problems

Alan Frieze, Carnegie Mellon University; and Gregory B. Sorkin, IBM T.J. Watson Center

10:15 AM Approximation Algorithms for Data Placement in Arbitrary Networks

Ivan D. Baev and Rajmohan Rajaraman, Northeastern University

Session 9B
9:00 AM Polynomial-Time Approximation Schemes for Geometric Graphs

Thomas Erlebach, Computer Engineering and Networks Laboratory, Switzerland; Klaus Jansen and Eike Seidel Christian-Albrechts-University of Kiel, Germany

9:25 AM Morphing between Polylines

Alon Efrat, The University of Arizona; Sariel Har-Peled, Duke University; Leonidas J. Guibas, Stanford University and T.M. Murali, Compaq Computer Corporation

9:50 AM Fast Implementation of Depth Contours using Topogical Sweep

Kim Miller, Tufts University; Suneeta Ramaswami, Rutgers University, Camden; Peter Rousseeuw, U.I.A., Belgium; Toni Sellarès, Universitat de Girona, Spain; Diane Souvaine, Tufts University; Ileana Streinu, Smith College; and Anja Struyf, U.I.A., Belgium

10:15 AM Computing the Depth of a Flat

Marshall Bern, Xerox PARC; and David Eppstein, University of California, Irvine

Session 9C
9:00 AM Which Formulae Shrink Under Random Restrictions?

Hana Chockler, The Hebrew University, Israel; and Uri Zwick, Tel Aviv University, Israel

9:25 AM Selective Families, Superimposed Codes, and Broadcasting on Unknown Radio Networks

Andrea E.F. Clementi, Università di Roma "Tor Vergata", Italy; Angelo Monti, Università "La Sapienza" di Roma, Italy; and Riccardo Silvestri, Università de L'Aquila, Italy

9:50 AM Adversarial Models in Evolutionary Game Dynamics

G. Istrate, M.V. Marathe,Los Alamos National Laboratory; and S.S. Ravi, SUNY at Albany

10:15 AM The Phase Transition in 1-in-k SAT and NAE 3-SAT

Dimitri Achlioptas, Microsoft Research; Arthur Chtcherba, University of New Mexico; Gabriel Istrate, Los Alamos National Laboratory; and Cristopher Moore, University of New Mexico

Session 10
Invited Presentation - Guessing Secrets

We consider a variant of the familiar "20 questions" problem in which one tries to discover the identity of some unknown "secret" by asking binary questions. In this variation, there is now a set of two (or more) secrets. For each question asked, an adversary gets to choose which of the secrets to use in supplying the answer, which in any case must be truthful. We will describe a number of algorithms for dealing with this problem, although we are still far from a complete understanding of the situation. Problems of this type have recently arisen in connection with certain Internet traffic routing applications.

Ronald L. Graham, University of California, San Diego, USA

1:45 PM � 3:50 PM
Concurrent Sessions

Session 11A
1:45 PM Can Entropy Characterize Performance of Online Algorithms?

Gopal Pandurangan and Eli Upfal, Brown University

2:10 PM Competitive Auctions and Digital Goods

Andrew V. Goldberg, InterTrust Technologies Corporation; Jason D. Hartline, University of Washington; and Andrew Wright, InterTrust Technologies Corporation

2:35 PM Towards Understanding the Predictability of Stock Markets from the Perspective of Computational Complexity

James Aspnes, Yale University; David F. Fischer, Yale College; Michael J. Fischer, Ming-Yang Kao and Alok Kumar, Yale University

3:00 PM Performance Guarantee for Online Deadline Scheduling in the Presence of Overload

Tak-Wah Lam and Kar-Keung To, University of Hong Kong, Hong Kong

Cancelled 3:25 PM Assigning Chain-like Tasks to a Chain-like Network

Gerhard J. Woeginger, Institut für Mathematick B, TU Graz, Austria

Session 11B
1:45 PM The Inverse Nearest Neighbor Problem with Astrophysical Applications

Richard Anderson and Brian Tjaden, University of Washington

2:10 PM Reductions Among High Dimensional Proximity Problems

Ashish Goel, University of Southern California; Piotr Indyk, MIT; and Kasturi Varadarajan, University of Iowa

2:35 PM A Cell Probe Lower Bound for Dynamic Nearest-neighbour Searching

Stephen Alstrup, IT University of Copenhagen, Denmark; Thore Husfeldt, Lund University, Sweden; and Theis Rauhe, IT University of Copenhagen, Denmark

3:00 PM Shape Matching using Edit-distance: An Implementation

Philip N. Klein, Thomas B. Sebastian and Benjamin B. Kimia, Brown University

3:25 PM On Validating Planar Worlds

Vida Dujmovic; and Sue Whitesides, McGill University, Canada

Session 11C
1:45 PM Improved Fast Integer Sorting in Linear Space

Yijie Han, University of Missouri at Kansas City

2:10 PM Single-Source Shortest-Paths on Arbitrary Directed Graphs in Linear Average-Case Time

Ulrich Meyer, Max-Planck-Institut für Informatik, Germany

2:35 PM Optimal Constrained Graph Exploration

Christian A. Duncan, University of Miami; Stephen G. Kobourov, University of Arizona; and V. S. Anil Kumar, Max-Planck-Institut für Informatick, Germany

3:00 PM An Efficient Algorithm for the Configuration Problem of Dominance Graphs

Ernst Althaus, Max-Planck-Institute for Computer Science, Germany; Denys Duchier, Alexander Koller, Universität des Saarlandes, Germany; Kurt Mehlhorn, Max-Planck-Institute for Computer Science, Germany; Joachim Niehren, Universität des Saarlandes, Germany; and Sven Thiel, Max-Planck-Institute for Computer Science, Germany

3:25 PM Linear Reductions of Maximum Matching

Therese Biedl, University of Waterloo, Canada

4:15 PM � 6:20 PM
Concurrent Sessions

Session 12A
4:15 PM Internet Packet Filter Management and Rectangle Geometry

David Eppstein, University of California, Irvine; and S. Muthukrishnan, AT&T Labs

4:40 PM Faster Kinetic Heaps and Their Use in Broadcast Scheduling

Haim Kaplan, Tel Aviv University, Israel; Robert E. Tarjan, InterTrust Technologies and Princeton University; and Kostas Tsioutsiouliklis, Princeton University

5:05 PM Finding Least Common Ancestors in Directed Acyclic Graphs

Michael A. Bender, Giridhar Pemmasani, Steven Skiena, and Pavel Sumazin, State University of New York at Stony Brook

5:30 PM On Binary Searching with Non-Uniform Costs

Eduardo S. Laber, PESC/COPPE, Universidade Federal do Rio de Janeiro, Brazil; and Ruy L. Milidiú, Artur A. Pessoa, Departamento de Informática, PUC-Rio, Brazil

5:55 PM Soft Kinetic Data Structures

Artur Czumaj, New Jersey Institute of Technology; and Christian Sohler, University of Paderborn, Germany

Session 12B
4:15 PM Testing Graphs for Colorability Properties

Eldar Fischer, NEC Research Institute

4:40 PM Random Lifts of Graphs

Alon Amit; Nathan Linial; Jiri Matousek; and Eyal Rozenman

5:05 PM Improved Results for Route Planning in Stochastic Transportation Networks

Justin Boyan, NASA Ames Research Center; and Michael Mitzenmacher, Harvard University

5:30 PM Hill-Climbing Finds Random Planted Bisections

Ted Carson and Russell Impagliazzo, University of California, San Diego

5:55 PM On Universally Easy Classes for NP-complete Problems

Erik D. Demaine, University of Waterloo, Canada; Alejandro López-Ortiz, University of New Brunswick, Canada; and J. Ian Munro, University of Waterloo, Canada

Session 12C
4:15 PM The Diameter of Random Massive Graphs

Linyuan Lu, University of California, San Diego

4:40 PM Domatic Partitions and the Lovász Local Lemma

Aravind Srinivasan, Bell Laboratories, Lucent Technologies

5:05 PM Equitable Colorings Extend Chernoff-Hoeffding Bounds

Sriram V. Pemmaraju, The University of Iowa

5:30 PM Universal Configurations in Light-Flipping Games

Yevgeniy Dodis, MIT; and Peter Winkler, Bell Labs

5:55 PM On the Discrete Bak-Sneppen Model of Self-organized Criticality

Jérémy Barbay and Claire Kenyon, Université Paris-Sud, France