List of accepted papers for SODA 2008: Weak epsilon-nets and interval chains Noga Alon and Haim Kaplan and Gabriel Nivasch and Micha Sharir and Shakhar Smorodinsky Optimal Universal Graphs with Deterministic Embedding Noga Alon and Michael Capalbo The Hiring Problem and Lake Wobegon Strategies Andrei Broder and Adam Kirsch and Ravi Kumar and Michael Mitzenmacher and Eli Upfal and Sergei Vassilvitskii Recognizing Partial Cubes in Quadratic Time David Eppstein Efficient reductions among lattice problems Daniele Micciancio Maximum overhang Mike Paterson and Yuval Peres and Mikkel Thorup and Peter Winkler and Uri Zwick Earth-Mover Distance over High Dimensional Spaces Alexandr Andoni and Piotr Indyk and Robert Krauthgamer Graph Balancing: A Special Case of Scheduling Unrelated Parallel Machines Tomas Ebenlendr and Marek Krcal and Jiri Sgall Incentive Compatible Regression Learning Ofer Dekel and Felix Fischer and Ariel D. Procaccia Metric Clustering via Consistent Labeling Robert Krauthgamer and Tim Roughgarden Nondecreasing paths in a weighted graph, or: How to optimally read a train schedule Virginia Vassilevska Cutting Cycles of Rods in Space: Hardness Results and Approximation Algorithms Boris Aronov and Mark de Berg and Chris Gray and Elena Mumford Iterated Rounding Algorithms for the Smallest k-Edge Connected Spanning Subgraph Harold Gabow and Suzanne Gallagher Real-Time Indexing over Fixed Finite Alphabets Amihood Amir and Igor Nor Algorithms for the Coalitional Manipulation Problem Michael Zuckerman and Ariel D. Procaccia and Jeffrey S. Rosenschein Improved Algorithms for Fully Dynamic Geometric Spanners and Geometric Routing Lee-Ad Gottlieb and Liam Roditty Fully Polynomial Time Approximation Schemes for Stochastic Dynamic Programs Nir Halman, Diego Klabjan, Chung-Lun Li, James Orlin and David Simchi-Levi On the Value of Coordination in Network Design Susanne Albers On Clustering to Minimize the Sum of Radii Matt Gibson and Gaurav Kanade and Erik Krohn and Imran Pirwani and Kasturi Varadarajan Price Based Protocols For Fair Resource Allocation: Convergence Time Analysis and Extension to Leontief Utilities Ashish Goel and Hamid Nazerzadeh The Effect of Induced Subgraphs on Quasi-Randomness Asaf Shapira and Raphael Yuster Holographic Algorithms With Unsymmetric Signatures Jin-Yi Cai and Pinyan Lu Strongly Polynomial and Fully Combinatorial Algorithms for Bisubmodular Function Minimization S. Thomas McCormick and Satoru Fujishige Better bounds for online load balancing on unrelated machines Ioannis Caragiannis Estimators and Tail Bounds for Dimension Reduction in $l_\alpha$ $(0<\alpha\leq 2)$ Using Stable Random Projections Ping Li Reconstructing Phylogenetic Trees with Very Short Branches Ilan Gronau and Shlomo Moran and Sagi Snir The UGC hardness threshold of the Lp Grothendieck problem Assaf Naor Concatenated codes can achieve list-decoding capacity Venkatesan Guruswami and Atri Rudra On the Connectivity of Dynamic Random Geometric Graphs Josep Diaz and Dieter Mitsche and Xavier Perez Universality of random graphs Domingos Dellamonica Jr. and Yoshiharu Kohayakawa and Vojtech Rodl and Andrzej Rucinski Greedy Drawings of Triangulations Raghavan Dhandapani Approximation Algorithms for Labeling Hierarchical Taxonomies Yuval Rabani and Leonard Schulman and Chaitanya Swamy Fast approximation of the permanent for very dense problems. Mark Huber and Jenny Law Comparing the strength of query types in property testing: The case of testing $k$-colorability Ido Ben-Eliezer and Tali Kaufman and Michael Krivelevich and Dana Ron Designing Networks with Good Equilibria Ho-Lin Chen and Tim Roughgarden and Gregory Valiant Embedding Metric Spaces in their Intrinsic Dimension Ittai Abraham and Yair Bartal and Ofer Neiman Sampling Algorithms and Coresets for Lp Regression A. Dasgupta and P. Drineas and B. Harb and R. Kumar and M. W. Mahoney Improved Algorithmic Versions of the Lovasz Local Lemma Aravind Srinivasan Geodesic Delaunay Triangulations and Witness Complexes in the Plane Jie Gao and Leonidas J. Guibas and Steve Oudot and Yue Wang Two-phase Greedy Algorithms for Some Classes of Combinatorial Linear Programs Ulrich Faigle and Britta Peis Rapid Mixing of Gibbs Sampling on Graphs that are Sparse on Average Elchanan Mossel and Allan Sly Broadcast Scheduling: Algorithms and Complexity Jessica Chang and Thomas Erlebach and Renars Gailis and Samir Khuller Geometric clustering: fixed-parameter tractability and lower bounds with respect to the dimension Sergio Cabello and Panos Giannopoulos and Christian Knauer and Gunter Rote Approximating General Metric Distances Between a Pattern and a Text Klim Efremenko and Ely Porat Computing Large Matchings Fast Ignaz Rutter and Alexander Wolff Empty-Ellipse Graphs Olivier Devillers and Jeff Erickson and Xavier Goaoc Space-Efficient Dynamic Orthogonal Point Location, Segment Intersection, and Range Reporting Guy E. Blelloch L(2,1)-labelling of graphs Frederic Havet and Bruce Reed and Jean-Sebastien Sereni A Fractional Model for the Border Gateway Protocol (BGP) Penny Haxell and Gordon Wilfong Fast Load Balancing via Bounded Best Response Baruch Awerbuch and Yossi Azar and Rohit Khandekar Ultra-Low-Dimensional Embeddings for Doubling Metrics T-H. Hubert Chan and Anupam Gupta and Kunal Talwar Approximating TSP on Metrics with Bounded Global Growth T-H. Hubert Chan and Anupam Gupta SPREAD: An Adaptive Scheme for Redundant and Fair Allocations in Dynamic Heterogeneous Storage Systems Christian Scheideler and Mario Vodisek Fast dimension reduction using rademacher series on dual BCH codes Nir Ailon A Near-Linear Time Algorithm for Computing Replacement Paths in Planar Directed Graphs Yuval Emek and David Peleg and Liam Roditty On stars and Steiner stars Adrian Dumitrescu and Csaba D. Toth Minimum weight convex Steiner partitions Adrian Dumitrescu and Csaba D. Toth Splay Trees, Davenport-Schinzel Sequences, and the Deque Conjecture Seth Pettie Yet another algorithm for dense Maxcut: Go Greedy Claire Mathieu and Warren Schudy Arc-disjoint in-trees in directed graph Naoyuki Kamiyama and Naoki Katoh and Atsushi Takizawa Improved Distance Sensitivity Oracles Via Random Sampling Aaron Bernstein and David Karger Linked Decompositions of Networks and the Power of Choice in Polya Urns Henry Lin and Christos Amanatidis and Martha Sideri and Richard M. Karp and Christos H. Papadimitriou A Nearly Linear Time Algorithm For The Half Integral Disjoint Paths Packing Ken-ichi Kawarabayashi and Bruce Reed Deterministic Random Walks on Regular Trees Joshua Cooper and Benjamin Doerr and Tobias Friedrich and Joel Spencer Fast Asynchronous Byzantine Agreement and Leader Election with Full Information Bruce Kapron and David Kempe and Valerie King and Jared Saia and Vishal Sanwalani Analysis of Greedy Approximations with Nonsubmodular Potential Functions Ding-Zhu Du and Ronald L. Graham and Panos M. Pardalos and Peng-Jun Wan and Weili Wu and Wenbo Zhao Improved Algorithms for Orienteering and Related Problems Chandra Chekuri and Nitish Korula and Martin Pal Competitive Queue Management for Latency Sensitive Packets Amos Fiat and Yishay Mansour and Uri Nadav Exact and Efficient 2D-Arrangements of Arbitrary Algebraic Curves Arno Eigenwillig and Michael Kerber Online Assignment in a distributional model with applications to Adwords Allocations Gagan Goel and Aranyak Mehta Computing Excluded Minors Isolde Adler and Martin Grohe and Stephan Kreutzer A Tight Lower Bound for Parity in Noisy Communication Networks Chinmoy Dutta and Yashodhan Kanoria and D. manjunath and Jaikumar Radhakrishnan Unconditionally Reliable Message Transmission in Directed Networks Bhavani Shankar and Prasant Gopal and Kannan Srinathan and C. Pandu Rangan Approximating Geometric Coverage Problems Thomas Erlebach, Erik Jan van Leeuwen Why Simple Hash Functions Work: Exploiting the Entropy in a Data Stream Michael Mitzenmacher and Salil Vadhan Catalan Structures and Dynamic Programming in $H$-minor-free graphs Frederic Dorn and Fedor V. Fomin and Dimitrios M. Thilikos Fast Algorithms for Finding Proper Strategies in Game Trees Peter Bro Miltersen and Troels Bjerre Sorensen Maintaining Deforming Surface Meshes Siu-Wing Cheng and Tamal K. Dey Clustering for Metric and Non-Metric Distance Measures Marcel R. Ackermann and Johannes Blömer and Christian Sohler On Distance to Monotonicity and Longest Increasing Subsequence of a Data Stream Funda Ergun and Hossein Jowhari Online Make-to-Order Joint Replenishment Model: Primal Dual Competitive Algorithms Niv Buchbinder and Tracy Kimbrel and Retsef Levi and Konstantin Makarychev and Maxim Sviridenko Approximating Connected Facility Location Problems via Random Facility Sampling and Core Detouring Friedrich Eisenbrand and Fabrizio Grandoni and Thomas Rothvoss and Guido Schaefer Finding one tight cycle Sergio Cabello and Matt DeVos and Jeff Erickson and Bojan Mohar Succinct Approximate Convex Pareto Curves Ilias Diakonikolas and Mihalis Yannakakis Adaptive Local Ratio Julian Mestre Algorithms for Distributed, Functional Monitoring Graham Cormode and S. Muthukrishnan and Ke Yi Fast Edge Splitting and Edmonds' Arborescence Construction for Unweighted Graphs Anand Bhalgat and Ramesh Hariharan and Telikepalli Kavitha and Debmalya Panigrahi Matroid Intersection, Pointer Chasing, and Young's Seminormal Representation of S_n Nicholas J. A. Harvey Product growth in finite groups Laszlo Babai and Nikolay Nikolov and Laszlo Pyber Trace reconstruction with constant deletion probability and related results Thomas Holenstein and Michael Mitzenmacher and Rina Panigrahy and Udi Wieder Finding an Optimal Tree Searching Strategy in Linear Time Shay Mozes and Krzysztof Onak and Oren Weimann Fully Dynamic Algorithm for Graph Spanners with Poly-logarithmic update time. Surender Baswana and Soumojit Sarkar Tight Lower Bounds for Selection in Randomly Ordered Streams Amit Chakrabarti and Sudipto Guha and T. S. Jayram and Mihai Patrascu Ascending Auctions for Integral (Poly)Matroids with Concave Increasing Separable Values Sushil Bikhchandani and Sven de Vries and James Schummer and Rakesh V. Vohra Non-Clairvoyant Scheduling with Precedence Constraints Julien Robert and Nicolas Schabanel (Almost) Optimal Coordination Mechanisms for Unrelated Machine Scheduling Yossi Azar and Kamal Jain and Vahab Mirrokni Distributed broadcase in unknown radio networks Gianluca De Marco Coresets, Sparse Greedy Approximation, and the Frank-Wolfe Algorithm Kenneth L. Clarkson Stochastic Analyses for Online Combinatorial Optimization Problems Naveen Garg and Anupam Gupta and Stefano Leonardi and Piotr Sankowski A Constant Factor Approximation Algorithm for k-Median Clustering with Outliers Ke Chen Auctions for Structured Procurement Matthew C. Cary and Abraham D. Flaxman and Jason D. Hartline and Anna R. Karlin In-Place 2-d Nearest Neighbor Search Timothy M. Chan and Eric Y. Chen A local algorithm for finding dense subgraphs Reid Andersen Almost Euclidean subspaces of $\ell_1^N$ via expander codes Venkatesan Guruswami and James R. Lee and Alexander Razborov On the Bichromatic $k$-Set Problem Timothy M. Chan The power of memory in randomized broadcasting Robert Elsaesser and Thomas Sauerwald A Deterministic Sub-linear Time Sparse Fourier Algorithm via Non-adaptive Compressed Sensing Methods M. A. Iwen A plant location guide for the unsure Barbara M. Anthony and Vineet Goyal and Anupam Gupta and Viswanath Nagarajan Provably Good Multicore Cache Performance for Divide-and-Conquer Algorithms Rezaul A. Chowdhury and Vijaya Ramachandran and Guy E. Blelloch and Phillip B. Gibbons and Shimin Chen and Michael Kozuch Dimension Augmentation and Combinatorial Criteria for Efficient Error-resistant DNA Self-Assembly Holin Chen and Ashish Goel and Chris Luhrs Set Connectivity Problems in Undirected Graphs and the Directed Steiner Network Problem Chandra Chekuri and Guy Even and Anupam Gupta and Danny Segev On Distributing Symmetric Streaming Computations Jon Feldman and S. Muthukrishnan and Anastasios Sidiropoulos and Cliff Stein and Zoya Svitkina Distribution-sensitive Point Location in Convex Subdivisions Sebastien Collette and Vida Dujmovic and John Iacono and Stefan Langerman and Pat Morin Ranged Hash Functions and the Price of Churn James Aspnes and Muli Safra and Yitong Yin On Properties of Random Dissections and Triangulations Nicla Bernasconi and Konstantinos Panagiotou and Angelika Steger Improved string reconstruction over insertion-deletion channels Krishnamurthy Viswanathan and Ram Swaminathan On the Approximability of Influence in Social Networks Ning Chen Parallel Monotonicity Reconstruction Michael Saks and C. Seshadhri An algorithm for improving graph partitions Reid Andersen and Kevin Lang Quasirandom Rumor Spreading Benjamin Doerr and Tobias Friedrich and Thomas Sauerwald The complexity of game dynamics: BGP oscillations, sink equlibria, and beyond Alex Fabrikant and Christos H. Papadimitriou Sampling Stable Marriages: Why Spouse-Swapping Won't Work Nayantara Bhatnagar and Sam Greenberg and Dana Randall Balls and bins with structure: Balanced allocations on hypergraphs P. Brighten Godfrey Robust Cost Colorings Takuro Fukunaga and Magnus M. Halldorsson and Hiroshi Nagamochi Dynamic Optimality for Skip Lists and B-Trees Karim Douieband Prosenjit Bose and Stefan Langerman PageRank and the Random Surfer model Prasad Chebolu and Pall Melsted Explicit constructions for compressed sensing of sparse signals Piotr Indyk Declaring Independence via the Sketching of Sketches Piotr Indyk and Andrew McGregor Delaunay graphs of point sets in the plane with respect to axis-parallel rectangles Xiaomin Chen and Janos Pach and Mario Szegedy and Gabor Tardos Load-Balanced Facility Location Zoya Svitkina Bounded Leg Distance and Reachability Oracles Ran Duan and Seth Pettie Charity Auctions on Social Networks Arpita Ghosh and Mohammad Mahdian Minimizing average latency in oblivious routing Prahladh Harsha and Thomas Hayes and Hariharan Narayanan and Harald Raecke and Jaikumar Radhakrishnan Noisy sorting without resampling Mark Braverman and Elchanan Mossel On Allocations that Maximize Fairness Uriel Feige