Program Information

The paper title and/or authors listed on the web program appear as originally received. All paper titles and authors will be listed
*correctly* in the final printed program distributed on-site.

Day

Date

Event

Session ID

Time

Title

Authors

Saturday


22-Jan

Registration


8:00 AM - 6:30 PM

ACM-SIAM SODA Welcome Reception

6:00 PM - 8:00 PM

Sunday

23-Jan


Registration Open

8:00 AM - 4:45 PM


Continental Breakfast

8:30 AM

Concurrent Sessions
9:00 AM - 11:05 AM

1A

9:00 AM

Dictionaries Using Variable-Length Keys and Data, with Applications

Daniel K. Blandford and Guy E. Blelloch

9:25 AM

Lower Bounds on the Size of Selection and Rank Indexes

Peter Bro Miltersen

9:50 AM

Dynamic Dictionary Matching and Compressed Suffix Trees

Ho-Leung Chan, Wing-Kai Hon, Tak-Wah Lam and Kunihiko Sadakane

10:15 AM

A Categorization Theorem on Suffix Arrays with Applications to Space-efficient Text Indexes

Meng He, J. Ian Munro and S. Srinivasa Rao

10:40 AM

Towards a Complete Characterization of Tries

G. Park and W. Szpankowski

Concurrent Sessions
9:00 AM - 11:05 AM

1B

9:00 AM

Inoculation Strategies for Victims of Viruses and the Sum-of-Squares Partition Problem

James Aspnes, Kevin Chang and Aleksandr Yampolskiy

9:25 AM

Marriage, Honesty, and Stability

Nicole Immorlica and Mohammad Mahdian

9:50 AM

Market Equilibria for Homothetic, Quasi-Concave Utilities and Economies of Scale in Production

Kamal Jain, Vijay V. Vazirani and Yinyu Ye

10:15 AM

On the Polynomial Time Computation of Equilibria for Certain Exchange Economies

Bruno Codenotti, Sriram Pemmaraju and Kasturi Varadarajan

10:40 AM

Computing Equilibria in Multi-Player Games

Christos H. Papadimitriou and Tim Roughgarden

Concurrent Sessions
9:00 AM - 11:05 AM

1C

9:00 AM

On Distance Scales, Embeddings, and Efficient Relaxations of the Cut Cone

James R. Lee

9:25 AM

An Improved Approximation to Sparsest Cut

Shuchi Chawla, Anupam Gupta and Harald Räcke

9:50 AM

The Complexity of Low-Distortion Embeddings Between Point Sets

Christos Papadimitriou and Shmuel Safra

10:15 AM

Approximation Algorithms for Low-Distortion Embeddings Into Low-Dimensional Spaces

Mihai Badoiu, Kedar Dhamdhere, Anupam Gupta, Yuri Rabinovich, Harald Raecke, R. Ravi and Anastasios Sidiropoulos

10:40 AM

A Tight Threshold for Metric Ramsey Phenomena

Moses Charikar and Adriana Karagiozova

Coffee Break

11:05 AM - 11:30 AM

Invited Plenary Session

2

11:30 AM - 12:30 PM

The Interface Between Computational and Combinatorial Geometry

Micha Sharir, Tel Aviv University, Israel

Luncheon

12:30 PM - 2:00 PM

Concurrent Sessions
2:00 PM - 4:05 PM

3A

2:00 PM

Multiple-source Shortest Paths in Planar Graphs

Philip N. Klein

2:25 PM

Computing the Shortest Path: A* Search Meets Graph Theory

Andrew Goldberg and Chris Harrelson

2:50 PM

Finding Large Cycles in Hamiltonian Graphs

Tomas Feder and Rajeev Motwani

3:15 PM

Approximating Connectivity Augmentation Problems

Zeev Nutov

3:40 PM

Primal-dual Approach for Directed Vertex Connectivity Augmentation and Generalizations

Laszlo A. Vegh and Andras A. Benczur

Concurrent Sessions
2:00 PM - 4:05 PM

3B

2:00 PM

Multidimensional Balanced Allocations

Andrei Broder and Michael Mitzenmacher

2:25 PM

Online Client-Server Load Balancing Without Global Information

Baruch Awerbuch, Mohammad T. Hajiaghayi, Robert Kleinberg and Tom Leighton

2:50 PM

Job Shop Scheduling with Unit Processing Times

Nikhil Bansal, Tracy Kimbrel and Maxim Sviridenko

3:15 PM

Approximating the Average Response Time in Broadcast Scheduling

Nikhil Bansal, Moses Charikar, Sanjeev Khanna and Joseph (Seffi) Naor

3:40 PM

An Improved Algorithm for Radio Broadcast

Michael Elkin and Guy Kortsarz

Concurrent Sessions
2:00 PM - 4:05 PM

3C

2:00 PM

On Levels in Arrangements of Surfaces in Three Dimensions

Timothy M. Chan

2:25 PM

Distributions of Points in the Unit-Square and Large k-Gons

Hanno Lefmann

2:50 PM

On Geometric Permutations Induced by Lines Transversal through a Fixed Point

Boris Aronov and Shakhar Smorodinsky

3:15 PM

Subgradient and Sampling Algorithms for L1 Regression

Kenneth L. Clarkson

3:40 PM

Approximation Hardness of Optimization Problems in Intersection Graphs of d-dimensional Boxes

Miroslav Chlebik and Janka Chlebikova

Coffee Break

4:05 PM - 4:30 PM

Concurrent Sessions
4:30 PM - 6:35 PM

4A

4:30 PM

Isomorphism and Embedding Problems for Infinite Limits of Scale-Free Graphs

Robert Kleinberg and Jon Kleinberg

4:55 PM

Adversarial Deletion in a Scale Free Random Graph Process

A. Flaxman, A. Frieze and J. Vera

5:20 PM

The Influence of Search Engines on Preferential Attachment

S. Chakrabarti, A. Frieze and J. Vera

5:45 PM

On the Spread of Viruses on the Internet

Noam Berger, Christian Borgs, Jennifer Chayes and Amin Saberi

6:10 PM

Analyzing and Characterizing Small-World Graphs

Van Nguyen and Chip Martel

Concurrent Sessions
4:30 PM - 6:35 PM

4B

4:30 PM

Substring Compression Problems

Graham Cormode and S. Muthukrishnan

4:55 PM

Optimizing Markov Models with Applications to Triangle Mesh Coding

Stefan Gumhold

5:20 PM

Dotted Interval Graphs and High Throughput Genotyping

Yonatan Aumann, Moshe Lewenstein, Oren Melamud, Ron Pinter and Zohar Yakhini

5:45 PM

Algorithms for Combining Rooted Triplets into a Galled Phylogenetic Network

Jesper Jansson, Nguyen Bao Nguyen and Wing-Kin Sung

6:10 PM

Unknotting is in AM ∩ co-AM

Masao Hara, Seiichi Tani and Makoto Yamamoto

Concurrent Sessions
4:30 PM - 6:35 PM

4C

4:30 PM

A Constant Approximation Algorithm for the One-Warehouse Multi-Retailer Problem

Retsef Levi, Robin O. Roundy and David B. Shmoys

4:55 PM

Sharing the Cost More Efficiently: Improved Approximation for Multicommodity Rent-or-Buy

L. Becchetti, J. Konemann, S. Leonardi and M. Pal

5:20 PM

Online Convex Optimization in the Bandit Setting: Gradient Descent Without a Gradient

Abraham D. Flaxman, Adam Tauman Kalai and H. Brendan McMahan

5:45 PM

Adaptivity and Approximation for Stochastic Packing Problems

Brian C. Dean, Michel X. Goemans and Jan Vondrak

6:10 PM

Theory of Semidefinite Programming for Sensor Network Localization

Anthony Man-Cho So and Yinyu Ye

Monday

24-Jan

Registration

8:00 AM - 4:45 PM

Continental Breakfast

8:30 AM

Concurrent Sessions
9:00 AM - 11:05 AM

5A

9:00 AM

An O(VE) Algorithm for Ear Decompositions of Matching Covered Graphs

Marcelo de Carvalho and Joseph Cheriyan

9:25 AM

Popular Matchings

David J. Abraham, Robert W. Irving, Telikepalli Kavitha and Kurt Mehlhorn

9:50 AM

Dominator Tree Verification and Vertex-Disjoint Paths in Digraphs

Loukas Georgiadis and Robert E. Tarjan

10:15 AM

Online Topological Ordering

Irit Katriel and Hans L. Bodlaender

10:40 AM

All Maximal Independent Sets and Dynamic Dominance for Sparse Graphs

David Eppstein

Concurrent Sessions
9:00 AM - 11:05 AM

5B

9:00 AM

LP Decoding Achieves Capacity

Jon Feldman and Cliff Stein

9:25 AM

Maximum-Likelihood Decoding of Reed-Solomon Codes is NP-hard

Venkatesan Guruswami and Alexander Vardy

9:50 AM

Collecting Correlated Information from a Sensor Network

Micah Adler

10:15 AM

Deterministic Network Coding by Matrix Completion

Nicholas J. A. Harvey, David R. Karger and Kazuo Murota

10:40 AM

Network Coding: Does the Model Need Tuning?

April Rasala Lehman and Eric Lehman

Concurrent Sessions
9:00 AM - 11:05 AM

5C

9:00 AM

Pianos Are Not Flat: Rigid Motion Planning in Three Dimensions

Vladlen Koltun

9:25 AM

A Constant-Factor Approximation Algorithm for Optimal Terrain Guarding

Boaz Ben-Moshe, Matthew J. Katz and Joseph S. B. Mitchell

9:50 AM

Ray Shooting amid Balls, Farthest Point from a Line, and Range Emptiness Searching

M. Sharir and H. Shaul

10:15 AM

Space-Time Tradeoffs for Approximate Spherical Range Counting

S. Arya, T. Malamatos and D. M. Mount

10:40 AM

Online Conflict-Free Coloring for Intervals

A. Fiat, M. Levy, J. Matousek, E. Mossel, J. Pach, M. Sharir, S. Smorodinsky, U. Wagner and E. Welzl

Coffee Break

11:05 AM - 11:30 AM

Invited Plenary Session

6

11:30 AM - 12:30 PM

Loop Quantum Gravity

John Baez, University of California, Riverside

Lunch (attendees on their own)

12:30 PM - 2:00 PM

Concurrent Sessions
2:00 PM - 4:05 PM

7A

2:00 PM

Approximation Algorithms for Cycle Packing Problems

Michael Krivelevich, Zeev Nutov and Raphael Yuster

2:25 PM

Approximating the Smallest k-edge Connected Spanning Subgraph by LP-Rounding

Harold N. Gabow, Michel X. Goemans, Eva Tardos and David P. Williamson

2:50 PM

Partial Covering of Hypergraphs

Ozgur Sumer

3:15 PM

Approximating Vertex Cover on Dense Graphs

Tomokazu Imamura and Kazuo Iwama

3:40 PM

Bidimensionality: New Connections between FPT Algorithms and PTASs

Erik D. Demaine and MohammadTaghi Hajiaghayi

Concurrent Sessions 2:00 PM - 4:05 PM

7B

2:00 PM

Limitations of Cross-monotonic Cost Sharing Schemes

Nicole Immorlica, Mohammad Mahdian and Vahab S. Mirrokni

2:25 PM

A Group-Strategyproof Mechanism for Steiner Forests

J. Koenemann, S. Leonardi and G. Schaefer

2:50 PM

Collusion-Resistant Mechanisms for Single-Parameter Agents

Andrew Goldberg and Jason Hartline

3:15 PM

A Multiple-Choice Secretary Problem With Applications To Online Auctions

Robert Kleinberg

3:40 PM

Rounds vs Queries Trade-off in Noisy Computation

Navin Goyal and Michael Saks

Concurrent Sessions
2:00 PM - 4:05 PM

7C

2:00 PM

Distributed Approaches to Triangulation and Embedding

Aleksandrs Slivkins

2:25 PM

Ordinal Embeddings of Minimum Relaxation: General Properties, Trees, and Ultrametrics

Mihai Bădoiu, Erik D. Demaine, Martin Farach-Colton, MohammadTaghi Hajiaghayi and Anastasios Sidiropoulos

2:50 PM

Sparse Source-wise and Pair-wise Distance Preservers

Don Coppersmith and Michael Elkin

3:15 PM

Lower Bound for Sparse Spanners

Pankaj K. Agarwal, Yusu Wang and Peng Yin

3:40 PM

New Constructions of (alpha, beta)-Spanners and Purely Additive Spanners

Surender Baswana, Telikepalli Kavitha, Kurt Mehlhorn and Seth Pettie

Coffee Break

4:05 PM - 4:30 PM

Concurrent Sessions
4:30 PM - 6:35 PM

8A

4:30 PM

Graphs Excluding a Fixed Minor have Grids as Large as Treewidth, with Combinatorial and Algorithmic Applications through Bidimensionality

Erik D. Demaine and MohammadTaghi Hajiaghayi

4:55 PM

Dissections and Trees, withs Applications to Optimal Mesh Encoding and to Random Sampling

Eric Fusy, Dominique Poulalhon and Gilles Schaeffer

5:20 PM

The Tutte Polynomial and the Expected Value of Random Minimal Length Spanning Tree of a Complete Graph

David Gamarnik

5:45 PM

Girth Restrictions for the 5-flow Conjecture

Martin Kochol

6:10 PM

Linear Equations, Arithmetic Progressions and Hypergraph Property Testing

Noga Alon and Asaf Shapira

Concurrent Sessions
4:30 PM - 6:35 PM

8B

4:30 PM

The Relative Worst Order Ratio Applied to Paging

Joan Boyar, Lene M. Favrholdt and Kim S. Larsen

4:55 PM

Strictly Convex Drawings of Planar Graphs

Günter Rote

5:20 PM

External-memory Exact and Approximate All-pairs Shortest-paths

Rezaul Alam Chowdhury and Vijaya Ramachandran

5:45 PM

Graph Distances in the Streaming Model: The Value of Space

Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri and Jian Zhang

6:10 PM

Lower Bounds for External Algebraic Decision Trees

Jeff Erickson

Concurrent Sessions
4:30 PM - 6:35 PM

8C

4:30 PM

On Hierarchical Routing in Bounded-Growth Metrics

Hubert T-H. Chan, Anupam Gupta, Bruce M. Maggs and Shuheng Zhou

4:55 PM

Fast Convergence of Selfish Rerouting

Eyal Even-Dar and Yishay Mansour

5:20 PM

Oblivious Routing on Node-Capacitated and Directed Graphs

Mohammad T. Hajiaghayi, Robert D. Kleinberg, Tom Leighton and Harald Raecke

5:45 PM

Distributed Online Call Control on General Networks

Harald Raecke and Adi Rosen

6:10 PM

An Optimal Online Algorithm for Packet Scheduling with Agreeable Deadlines

Fei Li, Jay Sethuraman and Clifford Stein

Business Meeting

7:00 PM - 8:00 PM

Tuesday

25-Jan

Registration

8:00 AM - 4:45 PM

Continental Breakfast

8:30 AM

Concurrent Sessions
9:00 AM - 11:05 AM

9A

9:00 AM

An Optimal Dynamic Interval Stabbing-Max Data Structure?

Pankaj K. Agarwal, Lars Arge and Ke Yi

9:25 AM

Self-Adjusting Top Trees

Robert E. Tarjan and Renato F. Werneck

9:50 AM

An Optimal Bloom Filter Replacement

Anna Pagh, Rasmus Pagh and S. Srinivasa Rao

10:15 AM

Efficient Hashing with Lookups in Two Memory Accesses

Rina Panigrahy

10:40 AM

Improved Range-Summable Random Variable Construction Algorithms

A. R. Calderbank, A. Gilbert, K. Levchenko, S. Muthukrishnan and M. Strauss

Concurrent Sessions
9:00 AM - 11:05 AM

9B

9:00 AM

A Spectral Heuristic for Bisecting Random Graphs

Amin Coja-Oghlan

9:25 AM

Complete Partitions of Graphs

Guy Kortsarz, Jaikumar Radhakrishnan and Sivaramakrisnan Sivasubramanian

9:50 AM

Two Algorithms for General List Matrix Partitions

Tomas Feder, Pavol Hell, Daniel Kral and Jiri Sgall

10:15 AM

On Lloyd's k-Means Method

Sariel Har-Peled and Bardia Sadri

10:40 AM

On Approximating the Depth and Related Problems

Boris Aronov and Sariel Har-Peled

Concurrent Sessions
9:00 AM - 11:05 AM

9C

9:00 AM

Multicoloring Unit Disk Graphs on Triangular Lattice Points

Yuichiro Miyamoto and Tomomi Matsui

9:25 AM

An Asymptotic Approximation Scheme for Multigraph Edge Coloring

Peter Sanders and David Steurer

9:50 AM

Computing Minimal Fill in O(n2.376 logn) Time

Pinar Heggernes, Jan Arne Telle and Yngve Villanger

10:15 AM

Finding the Shortest Bottleneck Edge in a Parametric Minimum Spanning Tree

Timothy M. Chan

10:40 AM

On the Random 2-stage Minimum Spanning Tree

Abraham D. Flaxman, Alan M. Frieze and Michael Krivelevich

Coffee Break

11:05 AM - 11:30 AM

Invited Plenary Session

10

11:30 AM - 12:30 PM

Rigorous Analysis of Heuristics for NP-hard Problems

Uriel Feige, Weizmann Institute, Israel

Lunch (attendees on their own)

12:30 PM - 2:00 PM

Concurrent Sessions
2:00 PM - 4:05 PM

11A

2:00 PM

An Improved Approximation Algorithm for Virtual Private Network Design

F. Eisenbrand and F. Grandoni

2:25 PM

Network Design for Information Networks

Ara Hayrapetyan, Chaitanya Swamy and Eva Tardos

2:50 PM

On the Approximability of Some Network Design Problems

Julia Chuzhoy, Anupam Gupta, Joseph (Seffi) Naor and Amitabh Sinha

3:15 PM

Approximating k-median with Non-uniform Capacities

Julia Chuzhoy and Yuval Rabani

3:40 PM

Improved Approximation for Universal Facility Location

Naveen Garg, Rohit Khandekar and Vinayaka Pandit

Concurrent Sessions
2:00 PM - 4:05 PM

11B

2:00 PM

The Cover Time of Two Classes of Random Graphs

Colin Cooper and Alan Frieze

2:25 PM

Coupling with the Stationary Distribution and Improved Sampling for Colorings and Independent Sets

Thomas P. Hayes and Eric Vigoda

2:50 PM

Sampling Regular Graphs and a Peer-to-peer Network

Colin Cooper, Martin Dyer and Catherine Greenhill

3:15 PM

The Bin-Covering Technique for Thresholding Random Geometric Graph Properties

S. Muthukrishnan and Gopal Pandurangan

3:40 PM

Random Planar Graphs with n Nodes and a Fixed Number of Edges

Stefanie Gerke, Colin McDiarmid, Angelika Steger and Andreas Weissl

Concurrent Sessions
2:00 PM - 4:05 PM

11C

2:00 PM

Provably Good Moving Least Squares

Ravikrishna Kolluri

2:25 PM

Manifold Reconstruction from Point Samples

Siu-Wing Cheng, Tamal K. Dey and Edgar A. Ramos

2:50 PM

Delaunay Triangulations Approximate Anchor Hulls

Tamal K. Dey, Joachim Giesen and Samrat Goswami

3:15 PM

Greedy Optimal Homotopy and Homology Generators

Jeff Erickson and Kim Whittlesey

3:40 PM

Controlled Perturbation for Delaunay Triangulations

Stefan Funke, Christian Klein, Kurt Mehlhorn and Susanne Schmitt

Coffee Break

4:05 PM - 4:30 PM

Concurrent Sessions
4:30 PM - 6:35 PM

12A

4:30 PM

Near-independence of Permutations and an Almost Sure Polynomial Bound on the Diameter of the Symmetric Group

Laszlo Babai and Thomas P. Hayes

4:55 PM

Matrix Rounding with Low Error in Small Submatrices

Benjamin Doerr

5:20 PM

Can We Reduce the Algebraic Eigen Problem to Polynomial Root-finding?

Victor Pan

5:45 PM

Optimal Random Number Generation from a Biased Coin

Sung-il Pae and Michael C. Loui

6:10 PM

A New Look at Survey Propagation and its Generalizations

Elitza Maneva, Elchanan Mossel and Martin J. Wainwright

Concurrent Sessions
4:30 PM - 6:35 PM

12B

4:30 PM

Coins Make Quantum Walks Faster

Andris Ambainis, Julia Kempe and Alexander Rivosh

4:55 PM

Quantum Algorithms for the Triangle Problem

Frederic Magniez, Miklos Santha and Mario Szegedy

5:20 PM

The Hidden Subgroup Problem and Permutation Group Theory

Julia Kempe and Aner Shalev

5:45 PM

Testing Hierarchical Systems

Damon Mosk-Aoyama and Mihalis Yannakakis

6:10 PM

Conformance Testing in the presence of Multiple Faults

Viraj Kumar and Mahesh Viswanathan

Concurrent Sessions
4:30 PM - 6:35 PM

12C

4:30 PM

Online Ascending Auctions for Gradually Expiring Items

Ron Lavi and Noam Nisan

4:55 PM

Near-Optimal Online Auctions

Avrim Blum and Jason Hartline

5:20 PM

On Profit-Maximizing Envy-Free Pricing

Venkatesan Guruswami, Jason Hartline, Anna Karlin, David Kempe, Claire Kenyon and Frank McSherry

5:45 PM

Improved Recommendation Systems

Baruch Awerbuch, Boaz Patt-Shamir, David Peleg and Mark Tuttle

6:10 PM

Selfish Routing with Atomic Players

Tim Roughgarden

Conference Adjourns

6:35 PM

 

 

 

 

 

 

 

 

 

 


Last Edited: 10/14/04
Created 3/18/04
DHTML Menus by http://www.milonic.com/