The paper title/and or authors listed here appear as originally received. All paper titles and authors will be listed correctly in the final printed program distributed on-site. FPTAS for Mixed-integer Polynomial Optimization with a Fixed Number of Variables J. A. De Loera, R. Hemmecke, 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, Jurek Czyzowicz, Zhicheng Gao, 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, Luca de Alfaro and Thomas A. Henzinger Distributed Selfish Load Balancing Petra Berenbrink, Tom Friedetzky, Leslie Ann Goldberg, Paul Goldberg, 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, Mordecai Golin, 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, Thomas Hackl, Clemens Huemer, Ferran Hurtado, 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, Uriel Feige, MohammadTaghi Hajiaghayi and Mohammad R. Salavatipour Randomized Online Algorithms for Minimum Metric Bipartite Matching Adam Meyerson, Akash Nanavati and Laura Poplawski Cache-Oblivious String Dictionaries Gerth Střlting Brodal and Rolf Fagerberg Superiority and Complexity of the Spaced Seeds Ming Li, Bin Ma and Zhang Louxin Bottleneck Links, Variable Demand, and the Tragedy of the Commons Richard Cole, Yevgeniy Dodis and Tim Roughgarden Morphing Orthogonal Planar Graph Drawings Anna Lubiw, 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, Mike Paterson and Uri Zwick Analyzing BitTorrent and Related Peer-to-Peer Networks David Arthur and Rina Panigrahy Finding Nucleolus of Flow Game Xiaotie Deng, Qizhi Fang and Xiaoxun Sun Trading Off Space for Passes in Graph Streaming Problems Camil Demetrescu, 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, Kevin Chen, Radu Mihaescu and Satish Rao Non-Cooperative Multicast and Facility Location Games Chandra Chekuri, Julia Chuzhoy, Liane Lewin-Eytan, Joseph (Seffi) Naor and Ariel Orda The Price of Being Near-Sighted Fabian Kuhn, 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, 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, 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 Antar Bandyopadhyay and David Gamarnik Improved Embeddings of Graph Metrics into Random Trees Kedar Dhamdhere, Anupam Gupta and Harald Raecke Directed Metrics and Directed Graph Partitioning Problems Moses Charikar, Konstantin Makarychev and Yury Makarychev Approximating Unique Games Anupam Gupta and Kunal Talwar On the Capacity of Information Networks Micah Adler, Nicholas J. A. Harvey, Kamal Jain, 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, S.P. Fekete, 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, Rorbert D. Kleinberg, Tom Leighton and Harald Raecke Single-Value Combinatorial Auctions and Implementation in Undominated Strategies Moshe Babaioff, 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, Luis Rademacher, Santosh Vempala and Grant Wang Upper Degree-Constrained Partial Orientations Harold N. Gabow Local versus Global Properties of Metric Spaces Sanjeev Arora, Laszlo Lovasz, Ilan Newman, Yuval Rabani and Santosh Vempala A Computational Study of External-Memory BFS Algorithms Deepak Ajwani, 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, 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, Tali Kaufman, 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, Don Coppersmith and Maxim Sviridenko Weighted Isotonic Regression under $L_1$ Norm Stanislav Angelov, Boulos Harb, 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, Stefan Eilts, Eyal Even-Dar, Yishay Mansour and Liam Roditty Streaming and Sublinear Approximation of Entropy and Information Distances Sudipto Guha, Andrew McGregor and Suresh Venkatasubramanian Leontief Economies Encode NonZero Sum Two-Player Games B. Codenotti, A. Saberi, 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, 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, Bernard Chazelle, Seshadhri Comandur and Ding Liu Approximating the k-Multicut Problem Daniel Golovin, 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, Yonatan Aumann, Gary Benson, Avivit Levy, Ohad Lipsky, Ely Porat, 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 and K.S. Liu Oblivious String Embeddings and Edit Distance Approximations Tugkan Batu, Funda Ergun and Cenk Sahinalp Anisotropic Surface Meshing Siu-Wing Cheng, Tamal K. Dey, Edgar A. Ramos and Rephael Wenger Max-Tolerance Graphs as Intersection Graphs: Cliques, Cycles, and Recognition Michael Kaufmann, Jan Kratochvil, 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, Daniel Stefankovic, 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, Michael J. Nelson and Jonathan Z. Sun Lower Bounds for Asymmetric Communication Channels and Distributed Source Coding Micah Adler, Erik D. Demaine, Nicholas J. A. Harvey and Mihai Patrascu Scalable Leader Election Valerie King, Jared Saia, 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, Ryan Williams and Shan Leung Maverick Woo Oblivious Network Design Anupam Gupta, 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, Robert Kleinberg and Tom Leighton Sampling Binary Contingency Tables with a Greedy Start Ivona Bezakova, Nayantara Bhatnagar and Eric Vigoda Sampling Algorithms for $\ell_2$ Regression and Applications to Matrix Approximation Petros Drineas, Michael W. Mahoney and S. Muthukrishnan The Hunting of the Bump: On Maximizing Statistical Discrepancy Deepak Agarwal, Jeff Phillips and Suresh Venkatasubramanian Analysis of Incomplete Data and an Inner-Dimension Helly Theorem Jie Gao, Michael Langberg and Leonard J. Schulman Dynamic Competitive Binary Search Trees Chengwen Chris Wang, Jonathan Derryberry and Daniel Sleator Trees, Markov convexity, and Finding Near-optimal Embeddings James R. Lee, Assaf Naor and Yuval Peres An Algorithmic Friedman-Pippenger Theorem on Tree Embeddings and Applications to Routing Domingos Dellamonica Jr. and Yoshiharu Kohayakawa Finding Large Sticks and Potatoes in Polygons Olaf Hall-Holt, Matthew Katz, Piyush Kumar, 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, 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, Lisa Fleischer and Atri Rudra 8/7-Approximation Algorithm for 1,2-TSP Piotr Berman and 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, 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