Papers Accepted to SODA 2006 ---------------------------- FPTAS for mixed-integer polynomial optimization with a fixed number of variables J. A. De Loera and R. Hemmecke and M. Koeppe and R. Weismantel Critical chromatic number and the complexity of perfect packings in graphs Daniela Kuehn and Deryk Osthus Simultaneous Diagonal Flips in Plane Triangulations Prosenjit Bose and Jurek Czyzowicz and Zhicheng Gao and Pat Morin and David R. Wood Quantum Verification of Matrix Products Harry Buhrman and Robert Spalek Efficient Construction of Unit Circular-Arc Models Min Chih Lin and Jayme L. Szwarcfiter The Complexity of Quantitative Concurrent Parity Games Krishnendu Chatterjee and Luca de Alfaro and Thomas A. Henzinger Distributed Selfish Load Balancing Petra Berenbrink and Tom Friedetzky and Leslie Ann Goldberg and Paul Goldberg and Zengjian Hu and Russell Martin Finding the Depth Order of Fat Objects Mark de Berg and Chris Gray The Knuth-Yao Quadrangle-Inequality Speedup is a Consequence of Total-Monotonicity Wolfgang Bein and Mordecai Golin and Larry Larmore and Yan Zhang Cake Cutting Really is Not a Piece of Cake Jeff Edmonds and Kirk Pruhs On The Chromatic Number of Some Geometric Hypergraphs Shakhar Smorodinsky A polynomial algorithm to find an independent set of maximum weight in a fork-free graph Vadim V. Lozin and Martin Milanic On the Number of Plane Graphs Oswin Aichholzer and Thomas Hackl and Clemens Huemer and Ferran Hurtado and Hannes Krasser and Birgit Vogtenhuber An Improved Approximation Algorithm for Combinatorial Auctions with Submodular Bidders Shahar Dobzinski and Michael Schapira Balanced Allocation on Graphs Krishnaram Kenthapadi and Rina Panigrahy Entropy based Nearest Neighbor Search in High Dimensions Rina Panigrahy Correlation Clustering with a Fixed Number of Clusters Ioannis Giotis and Venkatesan Guruswami Spanners for Doubling Metrics with Small Hop Diameter T-H. Hubert Chan and Anupam Gupta Combination Can Be Hard: Approximability of the Unique Coverage Problem Erik D. Demaine and Uriel Feige and MohammadTaghi Hajiaghayi and Mohammad R. Salavatipour Randomized Online Algorithms for Minimum Metric Bipartite Matching Adam Meyerson, Akash Nanavati, Laura Poplawski Cache-Oblivious String Dictionaries Gerth Střlting Brodal and Rolf Fagerberg Superiority and complexity of the spaced seeds Ming Li, Bin Ma andZhang Louxin Bottleneck Links, Variable Demand, and the Tragedy of the Commons Richard Cole and Yevgeniy Dodis and Tim Roughgarden Morphing Orthogonal Planar Graph Drawings Anna Lubiw and Mark Petrick and Michael J. Spriggs Metric Cotype Manor Mendel and Assaf Naor Tight Bounds on Probabilistic Embedding of Series-Parallel Graphs Yuval Emek and David Peleg Overhang Mike Paterson and Uri Zwick A Deterministic Subexponential Algorithm for Solving Parity Games Marcin Jurdzi\'{n}ski and Mike Paterson and Uri Zwick Analyzing BitTorrent and Related Peer-to-Peer Networks David Arthur and Rina Panigraphy Finding Nucleolus of Flow Game Xiaotie Deng and Qizhi Fang and Xiaoxun Sun Trading off space for passes in graph streaming problems Camil Demetrescu and Irene Finocchi and Andrea Ribichini An O(n log n) algorithm for maximum st-flow in a directed planar graph Glencora Borradaile and Philip Klein Four point conditions and exponential neighborhoods for the symmetric TSP V.Deineko and B.Klinz and G.Woeginger On the Number of Crossing-Free Matchings, (Cycles, and Partitions) Micha Sharir and Emo Welzl On the tandem duplication-random loss model of genome rearrangement Kamalika Chaudhuri and Kevin Chen and Radu Mihaescu and Satish Rao Non-Cooperative Multicast and Facility Location Games Chandra Chekuri and Julia Chuzhoy and Liane Lewin-Eytan and Joseph (Seffi) Naor and Ariel Orda The Price of Being Near-Sighted Fabian Kuhn and Thomas Moscibroda and Roger Wattenhofer Searching in dynamic three-dimensional convex hulls and planar Voronoi diagrams, and approximate range counting Haim Kaplan and Micha Sharir Measure and Conquer: A Simple $O (2^{0.288\,n})$ Independent Set Algorithm Fedor Fomin and Fabrizio Grandoni and Dieter Kratsch Spanners and emulators with sublinear distance errors Mikkel Thorup and Uri Zwick A New Approach to Proving Upper Bounds for MAX-2-SAT Arist Kojevnikov and Alexander S. Kulikov Subgraph characterization of Red/Blue-Split Graphs and Konig Egervary Graphs. Ephraim Korach, Thanh Nguyen and Britta Wienand Design of Data Structures for Mergeable Trees Loukas Georgiadis and Robert E. Tarjan and Renato F. Werneck A Robust Maximum Completion Time Measure for Scheduling Moses Charikar and Samir Khuller Squeezing Succinct Data Structures into Entropy Bounds Kunihiko Sadakane and Roberto Grossi The Prize-Collecting Generalized Steiner Tree Problem Via A New Approach Of Primal-Dual Schema Kamal Jain and MohammadTaghi Hajiaghayi Solving Random Satisfiable 3CNF Formulas in Expected Polynomial Time Michael Krivelevich and Dan Vilenchik Revenue Maximization When Bidders Have Budgets Zoe Abrams DAG-width - Connectivity Measure for Directed Graphs Jan Obdrzalek Testing graph isomorphism Eldar Fischer and Arie Matsliah Counting without sampling. New algorithms for enumeration problems using statistical physics David Gamarnik Improved Embeddings of Graph Metrics into Random Trees Kedar Dhamdhere and Anupam Gupta and Harald Raecke Directed Metrics and Directed Graph Partitioning Problems Moses Charikar and Konstantin Makarychev and Yury Makarychev Approximating Unique Games Anupam Gupta and Kunal Talwar On the Capacity of Information Networks Micah Adler and Nicholas J. A. Harvey and Kamal Jain and Robert D. Kleinberg and April Rasala Lehman Computing sequential equilibria for two-player games Peter Bro Miltersen and Troels Bjerre Sorensen Deterministic boundary recognition and topology extraction for large sensor networks A. Kroeller and S.P. Fekete and D. Pfisterer and S. Fischer A simple GAP-canceling algorithm for the generalized maximum flow problem Mateo Restrepo and David P. Williamson Linear programming and unique sink orientations Bernd Gaertner and Ingo Schurr Implicit Dictionaries with O(1) Modifications per Update and Fast Search Gianni Franceschini and J. Ian Munro Certifying Large Branch-width Sang-il Oum and Paul Seymour New Lower Bounds for Oblivious Routing in Undirected Graphs Mohammad Taghi Hajiaghayi and Rorbert D. Kleinberg and Tom Leighton and Harald Raecke. Single-Value Combinatorial Auctions and Implementation in Undominated Strategies Moshe Babaioff and Ron Lavi and Elan Pavlov Facility Location with Hierarchical Facility Costs Zoya Svitkina and Eva Tardos Relating singular values and discrepancy of weighted directed graphs Steven Butler Matrix Approximation and Projective Clustering via Volume Sampling Amit Deshpande and Luis Rademacher and Santosh Vempala and Grant Wang Upper Degree-Constrained Partial Orientations Harold N. Gabow Local versus Global Properties of Metric Spaces Sanjeev Arora and Laszlo Lovasz and Ilan Newman and Yuval Rabani and Santosh Vempala A Computational Study of External-Memory BFS Algorithms Deepak Ajwani and Roman Dementiev and Ulrich Meyer A Semidefinite Programming Approach to Tensegrity Theory and Realizability of Graphs Anthony Man-Cho So and Yinyu Ye Scheduling Unit Tasks to Minimize the Number of Idle Periods: A Polynomial Time Algorithm for Offline Dynamic Power Management Philippe Baptiste Reducing Tile Complexity for Self-Assembly Through Temperature Programming Ming-Yang Kao and Robert Schweller Coresets for Approximating the Extent of Shallow Levels Pankaj K. Agarwal and Sariel Har-Peled and Hai Yu Efficient Algorithms for Substring Near Neighbor Problem Alexandr Andoni and Piotr Indyk Robbing the bandit blind: Less regret in online geometric optimization against an adaptive adversary. Varsha Dani and Thomas P. Hayes Testing Triangle-Freeness in General Graphs Noga Alon and Tali Kaufman and Michael Krivelevich and Dana Ron Constraint Solving via Fractional Edge Covers Martin Grohe and Dániel Marx Maintaining Significant Stream Statistics over Sliding Windows L.K. Lee and H.F. Ting Improved approximation algorithms for broadcast scheduling Nikhil Bansal and Don Coppersmith and Maxim Sviridenko Weighted Isotonic Regression under $L_1$ Norm Stanislav Angelov and Boulos Harb and Sampath Kannan and Li-San Wang Approximation Algorithms for Wavelet Transform Coding of Data Streams Sudipto Guha and Boulos Harb On Nash Equilibria for a Network Creation Game Susanne Albers and Stefan Eilts and Eyal Even-Dar and Yishay Mansour and Liam Roditty Streaming and Sublinear Approximation of Entropy and Information Distances Sudipto Guha and Andrew McGregor and Suresh Venkatasubramanian Leontief Economies Encode NonZero Sum Two-Player Games B. Codenotti and A. Saberi and K. Varadarajan and Y. Ye Equilibria for Economies with Production: Constant-Returns Technologies and Production Planning Constraints K. Jain and K. Varadarajan Asymmetric Balanced Allocation with Simple Hash Functions Philipp Woelfel On the Competitive Ratio of Evaluating Priced Functions Ferdinando Cicalese and Eduardo Sany Laber Improved space-optimal algorithm for estimating frequency moments of data streams Sumit Ganguly and Deepanjan Kesh and Chandan Saha An asymptotic approximation algorithm for 3D-strip packing Klaus Jansen and Roberto Solis-Oba Many distances in planar graphs Sergio Cabello Self-Improving Algorithms Nir Ailon AND Bernard Chazelle AND Seshadhri Comandur AND Ding Liu Approximating the k-Multicut Problem Daniel Golovin and Viswanath Nagarajan and Mohit Singh Computing Steiner Minimum Trees in Hamming Metric Ernst Althaus and Rouven Naujoks Pattern Matching with Address Errors: Rearrangement Distances Amihood Amir and Yonatan Aumann and Gary Benson and Avivit Levy and Ohad Lipsky and Ely Porat and S. Skiena and U. Vishne On $k$-Median Clustering in High Dimensions Ke Chen Extra unit-speed machines are almost as powerful as speedy machines for competitive flow time scheduling Ho-Leung Chan, T.W. Lam, K.S. Liu Oblivious String Embeddings and Edit Distance Approximations Tugkan Batu and Funda Ergun and Cenk Sahinalp Anisotropic Surface Meshing Siu-Wing Cheng and Tamal K. Dey and Edgar A. Ramos and Rephael Wenger Max-Tolerance Graphs as Intersecton Graphs: Cliques, Cycles, and Recognition Michael Kaufmann and Jan Kratochvil and Katharina Lehmann and Amarendran Subramanian The Space Complexity of Pass-Efficient Algorithms for Clustering Census Data Kevin L. Chang and Ravi Kannan Accelerating Simulated Annealing for Combinatorial Counting Ivona Bezakova and Daniel Stefankovic and Eric Vigoda and Vijay Vazirani Generating all vertices of a polyhedron is hard. Khachiyan, Boros, Borys, Elbassioni, Gurvich Cache-Oblivious Dynamic Programming Rezaul Alam Chowdhury and Vijaya Ramachandran The Rainbow Skip Graph: A Fault-Tolerant Constant-Degree Distributed Data Structure Michael T. Goodrich and Michael J. Nelson and Jonathan Z. Sun Lower Bounds for Asymmetric Communication Channels and Distributed Source Coding Micah Adler and Erik D. Demaine and Nicholas J. A. Harvey and Mihai Patrascu Scalable Leader Election Valerie King and Jared Saia and Vishal Sanwalani and Erik Vee On the diameter of Eulerian orientations of graphs Laszlo Babai Single-Minded Unlimited Supply Pricing on Sparse Instances Patrick Briest and Piotr Krysta Confronting Hardness Using A Hybrid Approach Virginia Vassilevska and Ryan Williams and Shan Leung Maverick Woo Oblivious Network Design Anupam Gupta and MohammadTaghi Hajiaghayi and Harald Raecke (Almost) Tight Approximation Algorithms for Maximizing General Assignment Problems Lisa K. Fleischer, Michel X. Goemans, Vahab S. Mirrokni and Maxim Sviridenko Improved Lower and Upper Bounds for Universal TSP in Planar Metrics Mohammad T. Hajiaghayi and Robert Kleinberg and Tom Leighton Sampling Binary Contingency Tables with a Greedy Start Ivona Bezakova and Nayantara Bhatnagar and Eric Vigoda Sampling Algorithms for $\ell_2$ Regression and Applications to Matrix Approximation Petros Drineas and Michael W. Mahoney and S. Muthukrishnan The Hunting of the Bump: On Maximizing Statistical Discrepancy Deepak Agarwal and Jeff Phillips and Suresh Venkatasubramanian Analysis of Incomplete Data and an Inner-Dimension Helly Theorem Jie Gao and Michael Langberg and Leonard J. Schulman Dynamic Competitive Binary Search Trees Chengwen Chris Wang and Jonathan Derryberry and Daniel Sleator Trees, Markov convexity, and finding near-optimal embeddings James R. Lee and Assaf Naor and Yuval Peres An algorithmic Friedman-Pippenger theorem on tree embeddings and applications to routing (Extended Abstract) Domingos Dellamonica Jr. and Yoshiharu Kohayakawa Finding Large Sticks and Potatoes in Polygons Olaf Hall-Holt and Matthew Katz and Piyush Kumar and Joseph S. B. Mitchell and Arik Sityon Slow mixing of Glauber dynamics via topological obstructions Dana Randall A Near-Tight Approximation Lower Bound and Algorithm for the Kidnapped Robot Problem Sven Koenig and Apurva Mudgal and Craig Tovey Knapsack Auctions Gagan Aggarwal and Jason Hartline Ordering by weighted number of wins gives a good ranking for weighted tournaments Don Coppersmith and Lisa Fleischer and Atri Rudra 8/7-Approximation Algorithm for 1,2-TSP Piotr Berman, Marek Karpinski A Dynamic Data Structure for 3-d Convex Hulls and 2-d Nearest Neighbor Queries Timothy M. Chan Tightening Non-simple Paths and Cycles on Surfaces \'Eric Colin de Verdi\`ere and Jeff Erickson All-Pairs Shortest Paths for Unweighted Undirected Graphs in o(mn) Time Timothy M. Chan The Complexity of Matrix Completion Nicholas J. A. Harvey and David R. Karger Query-Efficient Algorithms for Polynomial Interpoltion over Composites Parikshit Gopalan Anytime Algorithms for Multi-Armed Bandit Problems Robert Kleinberg Rank/Select Operations on Large Alphabets: a Tool for Text Indexing Alexander Golynski and Ian Munro and Srinivasa S. Rao Improved lower bounds for embeddings into L_1 Robert Krautghamer and Yuval Rabani A general approach for incremental approximation and hierarchical clustering Guolong Lin and Chandrashekhar Nagarajan and Rajmohan Rajaraman and David P. Williamson l_2^2 spreading metrics for vertex ordering problems Moses Charikar and MohammadTaghi Hajiaghayi and Howard Karloff and Satish Rao