Monday, October 14, 9:00 - 10:35

Session 1A Chair: Rajeev Motwani

Polynomial Time Approximation Scheme for Euclidean TSP and Other Geometric Problems
by Sanjeev Arora
The Regularity Lemma and Approximation Schemes for Dense Problems
by Alan Frieze and Ravi Kannan
A New Rounding Procedure for the Assignment Problem with Applications to Dense Graph Arrangement Problems
by Sanjeev Arora, Alan Frieze, and Haim Kaplan
A Fully Polynomial Time Approximation Scheme for Strip Packing
by Claire Kenyon and Eric Remila

Session 1B (Starts 9:25) Chair: Russell Impagliazzo

A Decision Procedure for Unitary Linear Quantum Cellular Automata
by Christoph Durr and Miklos Santha
Polynomial Simulations Of Decohered Quantum Computers
by D. Aharonov and M. Ben-Or
Fault-Tolerant Quantum Computation
by Peter W. Shor

Monday, 11:15 - 12:50

Session 2A Chair: David Karger

Single-Source Unsplittable Flow
by Jon Kleinberg
The Optimal Path-Matching Problem
by William H. Cunningham and James F. Geelen
Short Paths in Expander Graphs
by Jon Kleinberg and Ronitt Rubinfeld
Spectral Partitioning Works: Planar Graphs and Finite Element Meshes
by Daniel Spielman and Shang-Hua Teng

Session 2B Chair: Chee Yap

Computing Permanents Over Fields of Characteristic 3
by Grigory Kogan
Solving System of Polynomial Congruences Modulo a Large Prime
by Ming-Deh Huang and Yiu-Chung Wong
Median Selection Requires $(2 + \epsilon)n$ Comparisons
by Dorit Dor and Uri Zwick
Faster Deterministic Sorting and Searching in Linear Space
by Arne Andersson

Monday, 2:15 - 3:50

Session 3A Chair: Baruch Schieber

An Efficient Algorithm for Constructing Minimal Trellises for Codes over Abelian Groups
by Vijay V. Vazirani, Huzur Saran, and B. Sundar Rajan
Highly Fault-Tolerant Parallel Computation
by Daniel A. Spielman
Maximum Likelihood Decoding of Reed Solomon Codes
by Madhu Sudan
New Coding Techniques for Improved Bandwidth Utilization
by Micah Adler

Session 3B Chair: Sandy Irani

Probabilistic Approximations of Metric Spaces and its Algorithmic Applications
by Yair Bartal
Factoring Graphs to Bound Mixing Rates
by Neal Madras and Dana Randall
Sampling According to the Multivariate Normal Density
by Ravi Kannan and Guangxing Li
Load Balancing and Density Dependent Jump Markov Processes
by Michael Mitzenmacher

Monday, 4:30 - 5:45

Session 4A Chair: Tandy Warnow

Tree Data Structures for N-body Simulation
by Richard Anderson
Efficient Information Gathering on the Internet
by Oren Etzioni, Steve Hanks, Tao Jiang, Richard M. Karp, Omid Madani, and Orli Waarts
Approximate Option Pricing
by Prasad Chalasani, Somesh Jha, and Isaac Saias

Session 4B Chair: Dexter Kozen

Temporal Logic and Semidirect Products: An Effective Characterization of the Until Hierarchy
by Denis Therien and Thomas Wilke
Equivalence in Finite-Variable Logics is Complete for Polynomial Time
by Martin Grohe
Simplified and Improved Resolution Lower Bounds
by Paul Beame and Toniann Pitassi

Tuesday, October 15, 9:00 - 10:00

Session 5 Chair: Martin Tompa

Computationally Hard Algebraic Problems
by Michael Rabin

Tuesday, 10:30 - 12:05

Session 6A Chair: Tandy Warnow

Approximating Unweighted k-Connectivity via Matching
by Joseph Cheriyan and Ramakrishna Thurimella
A 3-Approximation for the Minimum Tree Spanning k Vertices
by Naveen Garg
An 8-Approximation Algorithm for the Subset Feedback Vertex Set Problem
by Guy Even, Seffi Naor, and Leonid Zosin
Efficient Approximate and Dynamic Matching of Patterns Using a Labeling Paradigm
by Suleyman Cenk Sahinalp and Uzi Vishkin

Session 6B Chair: Russell Impagliazzo

A Polynomial-Time Algorithm for Learning Noisy Linear Threshold Functions
by Avrim Blum, Alan Frieze, Ravi Kannan, and Santosh Vempala
Property Testing and its Connection to Learning and Approximation
by Oded Goldreich, Shafi Goldwasser, and Dana Ron
On the Applications of Multiplicity Automata in Learning
by Amos Beimel, Francesco Bergadano, Nader H. Bshouty, Eyal Kushilevitz, and Stefano Varricchio
Learning Linear Transformations
by Alan Frieze, Mark Jerrum, and Ravi Kannan

Tuesday, 1:30 - 3:05

Session 7A Chair: S. Rao Kosaraju

Deterministic Routing with Bounded Buffers: Turning Offline into Online Protocols
by Friedhelm Meyer auf der Heide and Christian Scheideler
Universal Stability Results in Adversarial Queueing Theory
by Baruch Awerbuch, Antonio Fernandez, Jon Kleinberg, Tom Leighton, and Zhiyong Liu
A General Approach to Dynamic Packet Routing with Bounded Buffers
by Andrei Z. Broder, Alan M. Frieze, and Eli Upfal
Path Coloring on the Mesh
by Yuval Rabani

Session 7B Chair: Anne Condon

Discrepancy Sets and Pseudorandom Generators for Combinatorial Rectangles
by Roy Armoni, Michael Saks, Avi Wigderson, and Shiyu Zhou
The Boolean Isomorphism Problem
by Manindra Agrawal and Thomas Thierauf
Potential of the Approximation Method
by Kazuyuki Amano and Akira Maruoka
Static Dictionaries on AC^0 RAMs: Query Time Theta(sqrt(log n/log log n)) is Necessary and Sufficient
by Arne Andersson, Peter Bro Miltersen. Soren Riis, and Mikkel Thorup

Tuesday, 3:45 - 5:20

Session 8A Chair: Chee Yap

All Pairs Almost Shortest Paths
by Dorit Dor, Shay Halperin, and Uri Zwick
Computing Vertex Connectivity: New Bounds from Old Techniques
by Monika Rauch Henzinger, Satish Rao, and Hal N. Gabow
Better Lower Bounds for Halfspace Emptiness
by Jeff Erickson
Binary Search Partitions for Fat Rectangles
by Pankaj K. Agarwal, Edward F. Grove, T. M. Murali, and Jeffrey Scott Vitter

Session 8B Chair: Carsten Lund

On the Knowledge Complexity of NP
by Erez Petrank and Gabor Tardos
Incoercible Multiparty Computation
by Ran Canetti and Rosario Gennaro
Pseudorandom Functions Revisited: The Cascade Construction
by Mihir Bellare, Ran Canetti, and Hugo Krawczyk
The Geometry of Coin-Weighing Problems
by Noga Alon, Dmitry N. Kozlov, and Van H. Vu

Wednesday, October 16, 9:00 - 10:00

Session 9 Chair: Rajeev Motwani

Universal Data Compression and Portfolio Selection
by Tom Cover

Wednesday, 10:30 - 12:30

Session 10A Chair: Sandy Irani

Near-Optimal Parallel Prefetching and Caching
by Tracy Kimbrel and Anna Karlin
New Algorithms for the Disk Scheduling Problem
by Matthew Andrews, Michael A. Bender, and Lisa Zhang
Optimal Interval Management in External Memory
by Lars Arge and Jeffrey Scott Vitter
Fast Fault-Tolerant Concurrent Access to Shared Objects
by C. G. Plaxton and R. Rajaraman
Fault Tolerant Data Structures
by Yonatan Aumann and Michael Bender

Session 10B Chair: Michael Luby

Approximate Checking of Polynomials and Functional Equations
by Funda Ergun, S. Ravi Kumar, and Ronitt Rubinfeld
Efficient Self-Testing/Self-Correction of Linear Recurrences
by S. Ravi Kumar and D. Sivakumar
Verifying Identities
by Sridhar Rajagopalan and Leonard J. Schulman
Gadgets, Approximation, and Linear Programming
by Luca Trevisan, Gregory B. Sorkin, Madhu Sudan, and David P. Williamson
Clique is Hard to Approximate Within $n^{1-\epsilon}$
by Johan Hastad