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