List of accepted papers for SODA 2005: Graphs Excluding a Fixed Minor have Grids as Large as Treewidth, with Combinatorial and Algorithmic Applications through Bidimensionality Erik D. Demaine and MohammadTaghi Hajiaghayi Approximating Connectivity Augmentation Problems Zeev Nutov Maximum-Likelihood Decoding of Reed-Solomon Codes is NP-hard Venkatesan Guruswami and Alexander Vardy Matrix Rounding with Low Error in Small Submatrices Benjamin Doerr An improved algorithm for radio broadcast Michael Elkin and Guy Kortsarz Network Coding: Does the Model Need Tuning? April Rasala Lehman and Eric Lehman On the random 2-stage minimum spanning tree Abraham D. Flaxman and Alan M. Frieze and Michael Krivelevich Efficient Hashing with Lookups in two Memory Accesses Rina Panigrahy Towards a Complete Characterization of Tries G. Park and W. Szpankowski Bidimensionality: New Connections between FPT Algorithms and PTASs Erik D. Demaine and MohammadTaghi Hajiaghayi Optimizing Markov Models with Applications to Triangle Mesh Coding Stefan Gumhold The cover time of two classes of random graphs Colin Cooper and Alan Frieze Oblivious Routing on Node-Capacitated and Directed Graphs Mohammad T. Hajiaghayi and Robert D. Kleinberg and Tom Leighton Computing Equilibria in Multi-Player Games Christos H. Papadimitriou and Tim Roughgarden Selfish Routing with Atomic Players Tim Roughgarden All Maximal Independent Sets and Dynamic Dominance for Sparse Graphs David Eppstein Pianos are not Flat: Rigid Motion Planning in Three Dimensions Vladlen Koltun Linear Equations, Arithmetic Progressions and Hypergraph Property Testing Noga Alon and Asaf Shapira Sparse Source-wise and Pair-wise Distance Preservers Don Coppersmith and Michael Elkin Delaunay Triangulations Approximate Anchor Hulls Tamal K. Dey and Joachim Giesen and Samrat Goswami Online Client-Server Load Balancing Without Global Information Baruch Awerbuch and Mohammad T. Hajiaghayi and Robert Kleinberg and Tom Leighton The hidden subgroup problem and permutation group theory Julia Kempe and Aner Shalev Approximating the smallest k-edge connected spanning subgraph by LP-Rounding Harold N. Gabow and Michel X. Goemans and Eva Tardos and David P. Williamson A Categorization Theorem on Suffix Arrays with Applications to Space-efficient Text Indexes Meng He and J. Ian Munro and S. Srinivasa Rao Approximation algorithms for cycle packing problems Michael Krivelevich and Zeev Nutov and Raphael Yuster Online Conflict-Free Coloring for Intervals A. Fiat and M. Levy and J. Matousek and E. Mossel and J. Pach and M. Sharir and S. Smorodinsky and U. Wagner and E. Welzl Improved Recommendation Systems Baruch Awerbuch, Boaz Patt-Shamir, David Peleg and Mark Tuttle Online Topological Ordering Irit Katriel and Hans L. Bodlaender On Geometric Permutations Induced by Lines Transversal through a Fixed Point Boris Aronov and Shakhar Smorodinsky Distributed Approaches to Triangulation and Embedding Aleksandrs Slivkins The Relative Worst Order Ratio Applied to Paging Joan Boyar, Lene M. Favrholdt, Kim S. Larsen On Lloyd's k-Means Method Sariel Har-Peled and Bardia Sadri Approximation Hardness of Optimization Problems in Intersection Graphs of d-dimensional Boxes Miroslav Chlebik and Janka Chlebikova Adversarial Deletion in a Scale Free Random Graph Process A. Flaxman, A. Frieze and J. Vera On Approximating the Depth and Related Problems Boris Aronov and Sariel Har-Peled Adaptivity and Approximation for Stochastic Packing Problems Brian C. Dean and Michel X. Goemans and Jan Vondrak Strictly convex drawings of planar graphs G\"unter Rote An O(VE) Algorithm for Ear Decompositions of Matching Covered Graphs Marcelo de Carvalho and Joseph Cheriyan An Improved Approximation to Sparsest Cut Shuchi Chawla and Anupam Gupta and Harald R\"acke Job shop scheduling with unit processing times Nikhil Bansal and Tracy Kimbrel and Maxim Sviridenko Quantum algorithms for the triangle problem Frederic Magniez and Miklos Santha and Mario Szegedy Girth restrictions for the 5-flow conjecture Martin Kochol Computing Minimal Fill in $O(n^{2.376} \log n)$ Time Pinar Heggernes and Jan Arne Telle and Yngve Villanger An Optimal Bloom Filter Replacement Anna Pagh and Rasmus Pagh and S. Srinivasa Rao A Constant Approximation Algorithm for the One-Warehouse Multi-Retailer Problem Retsef Levi and Robin O. Roundy and David B. Shmoys Collusion-Resistant Mechanisms for Single-Parameter Agents Andrew Goldberg and Jason Hartline Computing the Shortest Path: $A^*$ Search Meets Graph Theory Andrew Goldberg and Chris Harrelson Dominator Tree Verification and Vertex-Disjoint Paths in Digraphs Loukas Georgiadis and Robert E. Tarjan Coupling with the Stationary Distribution and Improved Sampling for Colorings and Independent Sets Thomas P. Hayes and Eric Vigoda Two algorithms for general list matrix partitions Tomas Feder and Pavol Hell and Daniel Kral and Jiri Sgall Complete Partitions of Graphs Guy Kortsarz and Jaikumar Radhakrishnan and Sivaramakrisnan Sivasubramanian Finding large cycles in Hamiltonian graphs Tomas Feder and Rajeev Motwani Sampling regular graphs and a peer-to-peer network Colin Cooper and Martin Dyer and Catherine Greenhill A new look at Survey propagation and its generalizations Elitza Maneva and Elchanan Mossel and Martin J. Wainwright Ray Shooting amid Balls, Farthest Point from a Line, and Range Emptiness Searching M. Sharir and H. Shaul Self-Adjusting Top Trees Robert E. Tarjan and Renato F. Werneck Improved Approximation for Universal Facility Location Naveen Garg and Rohit Khandekar and Vinayaka Pandit Online convex optimization in the bandit setting: gradient descent without a gradient Abraham D. Flaxman and Adam Tauman Kalai and H. Brendan McMahan Network Design for Information Networks Ara Hayrapetyan and Chaitanya Swamy and Eva Tardos An Asymptotic Approximation Scheme for Multigraph Edge Coloring Peter Sanders and David Steurer LP Decoding Achieves Capacity Jon Feldman and Cliff Stein Subgradient and Sampling Algorithms for L_1 Regression Kenneth L. Clarkson Limitations of cross-monotonic cost sharing schemes Nicole Immorlica and Mohammad Mahdian and Vahab S. Mirrokni Marriage, Honesty, and Stability Nicole Immorlica and Mohammad Mahdian Market Equilibria for Homothetic, Quasi-Concave Utilities and Economies of Scale in Production Kamal Jain and Vijay V. Vazirani and Yinyu Ye An optimal online algorithm for packet scheduling with agreeable deadlines Fei Li and Jay Sethuraman and Clifford Stein Dotted interval graphs and high throughput genotyping Yonatan Aumann and Moshe Lewenstein and Oren Melamud and Ron Pinter and Zohar Yakhini A Spectral Heuristic for Bisecting Random Graphs Amin Coja-Oghlan Can we reduce the algebraic eigen problem to polynomial root-finding? Victor Pan Lower Bound for Sparse Spanners Pankaj K. Agarwal, Yusu Wang, Peng Yin Analyzing and Characterizing Small-World Graphs Van Nguyen and Chip Martel Primal-dual approach for directed vertex connectivity augmentation and generalizations Laszlo A. Vegh and Andras A. Benczur Provably Good Moving Least Squares Ravikrishna Kolluri Partial Covering of Hypergraphs Ozgur Sumer Substring Compression Problems Graham Cormode and S. Muthukrishnan Isomorphism and Embedding Problems for Infinite Limits of Scale-Free Graphs Robert Kleinberg and Jon Kleinberg The Tutte Polynomial and the expected value of random minimal length spanning tree of a complete graph David Gamarnik Ordinal Embeddings of Minimum Relaxation: General Properties, Trees, and Ultrametrics Mihai B\u{a}doiu and Erik D. Demaine and Martin Farach-Colton and MohammadTaghi Hajiaghayi and Anastasios Sidiropoulos On Profit-Maximizing Envy-Free Pricing Venkatesan Guruswami and Jason Hartline and Anna Karlin and David Kempe and Claire Kenyon and Frank McSherry Dynamic Dictionary Matching and Compressed Suffix Trees Ho-Leung Chan and Wing-Kai Hon and Tak-Wah Lam and Kunihiko Sadakane On distance scales, embeddings, and efficient relaxations of the cut cone James R. Lee Rounds vs Queries Trade-off in Noisy Computation Navin Goyal and Michael Saks The Bin-Covering Technique for Thresholding Random Geometric Graph Properties S. Muthukrishnan and Gopal Pandurangan Testing Hierarchical Systems Damon Mosk-Aoyama and Mihalis Yannakakis Multicoloring Unit Disk Graphs on Triangular Lattice Points Yuichiro Miyamoto and Tomomi Matsui Online Ascending Auctions for Gradually Expiring Items Ron Lavi and Noam Nisan Theory of Semidefinite Programming for Sensor Network Localization Anthony Man-Cho So and Yinyu Ye Sharing the cost more efficiently: Improved Approximation for Multicommodity Rent-or-Buy L. Becchetti and J. Konemann and S. Leonardi and M. Pal Lower bounds on the size of selection and rank indexes Peter Bro Miltersen Approximating k-median with non-uniform capacities Julia Chuzhoy and Yuval Rabani On the approximability of some network design problems Julia Chuzhoy and Anupam Gupta and Joseph (Seffi) Naor and Amitabh Sinha Algorithms for Combining Rooted Triplets into a Galled Phylogenetic Network Jesper Jansson and Nguyen Bao Nguyen and Wing-Kin Sung The Complexity of Low-Distortion Embeddings Between Point Sets Christos Papadimitriou and Shmuel Safra Space-Time Tradeoffs for Approximate Spherical Range Counting S. Arya and T. Malamatos and D. M. Mount UNKNOTTING is in AM \cap co-AM Masao Hara and Seiichi Tani and Makoto Yamamoto Fast Convergence of Selfish Rerouting Eyal Even-Dar and Yishay Mansour Popular Matchings David J. Abraham and Robert W. Irving and Telikepalli Kavitha and Kurt Mehlhorn Coins Make Quantum Walks Faster Andris Ambainis and Julia Kempe and Alexander Rivosh Manifold Reconstruction from Point Samples Siu-Wing Cheng and Tamal K. Dey and Edgar A. Ramos On the polynomial time computation of equilibria for certain exchange economies Bruno Codenotti and Sriram Pemmaraju and Kasturi Varadarajan An Optimal Dynamic Interval Stabbing-Max Data Structure? Pankaj K. Agarwal and Lars Arge and Ke Yi The influence of search engines on preferential attachment S. Chakrabarti and A. Frieze and J. Vera A Tight Threshold for Metric Ramsey Phenomena Moses Charikar and Adriana Karagiozova Dissections and trees, withs applications to optimal mesh encoding and to random sampling Eric Fusy and Dominique Poulalhon and Gilles Schaeffer Near-Optimal Online Auctions Avrim Blum and Jason Hartline Multidimensional Balanced Allocations Andrei Broder and Michael Mitzenmacher An improved approximation algorithm for virtual private network design F. Eisenbrand and F. Grandoni Inoculation Strategies for Victims of Viruses and the Sum-of-Squares Partition Problem James Aspnes and Kevin Chang and Aleksandr Yampolskiy A Constant-Factor Approximation Algorithm for Optimal Terrain Guarding Boaz Ben-Moshe and Matthew J. Katz and Joseph S. B. Mitchell Optimal Random Number Generation from a Biased Coin Sung-il Pae and Michael C. Loui A Group-Strategyproof Mechanism for Steiner Forests J. Koenemann and S. Leonardi and G. Schaefer Multiple-source shortest paths in planar graphs Philip N. Klein Lower Bounds for External Algebraic Decision Trees Jeff Erickson Distributions of Points in the Unit-Square and Large k-Gons Hanno Lefmann Distributed Online Call Control on General Networks Harald Raecke and Adi Rosen New Constructions of (alpha, beta)-Spanners and Purely Additive Spanners Surender Baswana and Telikepalli Kavitha and Kurt Mehlhorn and Seth Pettie Approximating the Average Response Time in Broadcast Scheduling Nikhil Bansal and Moses Charikar and Sanjeev Khanna and Joseph (Seffi) Naor On the Spread of Viruses on the Internet Noam Berger and Christian Borgs and Jennifer Chayes and Amin Saberi Graph Distances in the Streaming Model: The Value of Space Joan Feigenbaum and Sampath Kannan and Andrew McGregor and Siddharth Suri and Jian Zhang On Levels in Arrangements of Surfaces in Three Dimensions Timothy M. Chan Finding the shortest bottleneck edge in a parametric minimum spanning tree Timothy M. Chan Dictionaries Using Variable-Length Keys and Data, with Applications Daniel K. Blandford and Guy E. Blelloch Random planar graphs with n nodes and a fixed number of edges Stefanie Gerke and Colin McDiarmid and Angelika Steger and Andreas Weissl Controlled Perturbation for Delaunay Triangulations Stefan Funke and Christian Klein and Kurt Mehlhorn and Susanne Schmitt External-memory exact and approximate all-pairs shortest-paths Rezaul Alam Chowdhury and Vijaya Ramachandran Collecting Correlated Information from a Sensor Network Micah Adler Greedy Optimal Homotopy and Homology Generators Jeff Erickson and Kim Whittlesey Near-independence of permutations and an almost sure polynomial bound on the diameter of the symmetric group Laszlo Babai and Thomas P. Hayes On Hierarchical Routing in Bounded-Growth Metrics Hubert T-H. Chan and Anupam Gupta and Bruce M. Maggs and Shuheng Zhou Conformance Testing in the presence of Multiple Faults Viraj Kumar and Mahesh Viswanathan Deterministic Network Coding by Matrix Completion Nicholas J. A. Harvey and David R. Karger and Kazuo Murota Approximating Vertex Cover on Dense Graphs Tomokazu Imamura and Kazuo Iwama Improved Range-Summable Random Variable Construction Algorithms A. R. Calderbank and A. Gilbert and K. Levchenko and S. Muthukrishnan and M. Strauss A Multiple-Choice Secretary Problem With Applications To Online Auctions Robert Kleinberg Approximation Algorithms for Low-Distortion Embeddings Into Low-Dimensional Spaces Mihai Badoiu and Kedar Dhamdhere and Anupam Gupta and Yuri Rabinovich and Harald Raecke and R. Ravi and Anastasios Sidiropoulos