Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms
Edited by Dana Randall
Each link below is to a PDF of the paper as it was submitted. Papers are listed in program order. PDF file names represent the Proceedings (SODA and year 11), followed by order in printed version (e.g. 001) and first author's last name and first initial.
Table of Contents
Sessions:
1A 1B 1C 2 Best
Paper Presentation 3A 3B 3C 4A 4B 4C 5A 5B 5C 6 7A 7B 7C 8A 8B 8C 9A 9B 9C 10 11A 11B 11C 12A 12B 12C
1 Optimal Bounds for Johnson-Lindenstrauss Transforms and Streaming Problems with Sub-Constant Error
T. S. Jayram and David Woodruff
11 The Streaming Complexity of Cycle Counting, Sorting by Reversals, and Other Problems
Elad Verbin and Wei Yu
26 Streaming k-means on Well-Clusterable Data
Vladimir Braverman, Adam Meyerson, Rafail Ostrovsky, Alan Roytman, Michael Shindler, and Brian
Tagiku
41 Efficient Sketches for the Set Query Problem
Eric Price
57 Exponential Time Improvement for min-wise Based Algorithms
Guy Feigenblat, Ely Porat, and Ariel Shiftan
67 A simple and fast 2-approximation algorithms for the one-warehouse multi-retailers problem
Gautier Stauffer, Guillaume Massonet, Christophe Rapine, and Jean-Philippe Gayon
80 Generalized Machine Activation Problems
Jian Li and Samir Khuller
95 Online Scalable Algorithm for Minimizing ℓk-norms of Weighted Flow Time On Unrelated
Machines
Sungjin Im and Benjamin Moseley
109 Online Scalable Scheduling for the ℓk-norms of Flow Time Without Conservation of Work
Jeff Edmonds, Sungjim Im, Benjamin Moseley
120 Online Scheduling on Identical Machines using SRPT
Kyle Fox and Benjamin Moseley
129 A complete resolution of the Keller maximum clique problem
Jennifer Debroni, John D. Eblen, Michael A. Langston, Wendy Myrvold, Peter Shor, Dinesh
Weerapurage
136 On independent sets in random graphs
Amin Coja-Oghlan and Charilaos Efthymiou
145 Coloring random graphs online without creating monochromatic subgraphs
Torsten Mütze, Thomas Rast, and Reto Spöhel
159 The maximum size of a Sidon set contained in a sparse random set of integers
Yoshiharu Kohayakawa, Sangjune Lee, and Vojtĕch Rödl
172 On Buffon Machines and Numbers
Philippe Flajolet, Maryse Pelletier, and Michčle Soria
184 Graph Coloring via The Probabilistic Method
Bruce Reed
185 An Almost Optimal Unrestricted Fast Johnson-Lindenstrauss Transform
Nir Ailon and Edo Liberty
192 A Stackelberg Strategy for Routing Flow over Time
Umang Bhaskar, Lisa Fleischer, and Elliot Anshelevich
202 A subexponential lower bound for the Random Facet algorithm for Parity Games
Oliver Friedmann, Thomas Dueholm Hansen, and Uri Zwick
217 On Minmax Theorems for Multiplayer Games
Yang Cai and Constantinos Daskalakis
235 Near-Optimal No-Regret Algorithms for Zero-Sum Games
Constantinos Daskalakis, Alan Deckelbaum, and Anthony Kim
255 Local Smoothness and the Price of Anarchy in Atomic Splittable Congestion Games
Tim Roughgarden and Florian Schoppmann
268 I/O-Efficient Contour Queries on Terrains
Pankaj K. Agarwal, Thomas Mřlhave, and Bardia Sadri
285 Implicit Flow Routing on Terrains with Applications to Surface Networks and Drainage
Structures
Mark de Berg, Herman Haverkort, and Constantinos Tsirogiannis
297 Shortest Non-Crossing Walks in the Plane
Jeff Erickson and Amir Nayyeri
309 Computing Shortest Paths amid Pseudodisks
Danny Z. Chen and Haitao Wang
327 On the Complexity of Time-Dependent Shortest Paths
Luca Foschini, John Hershberger, and Subhash Suri
342 A Master Theorem for Discrete Divide and Conquer Recurrences
Michael Drmota and Wojciech Szpankowski
362 Optimal pattern matching in LZW compressed strings
Pawel Gawrychowski
373 Random Access to grammar-Compressed Strings
Philip Bille, Gad M. Landau, Rajeev Raman, Kunihiko Sadakane, Srinivasa Rao Satti, and Oren
Weimann
390 Ordered and Unordered Top-K Range Reporting in Large Data Sets
Peyman Afshani, Gerth Střlting Brodal, and Norbert Zeh
401 Top-K Color Queries for Document Retrieval
Marek Karpinski and Yakov Nekrich
412 Mobile Geometric Graphs: Detection, Coverage and Percolation
Yuval Peres, Alistair Sinclair, Perla Sousi, and Alexandre Stauffer
429 Randomized Diffusion for Indivisible Loads
Petra Berenbrink, Colin Cooper, Tom Friedetzky, Tobias Friedrich, and Thomas Sauerwald
440 Fast Information Spreading in Graphs with Large Weak Conductance
Keren Censor-Hillel and Hadas Shachnai
449 On the Randomness Requirements of Rumor Spreading
George Giakkoupis and Philipp Woelfel
462 Rumor Spreading and Vertex Expansion on Regular Graphs
Thomas Sauerwald and Alexandre Stauffer
476 Bin Packing via Discrepancy of Permutations
Friedrich Eisenbrand, Dömötör Pálvölgyi, and Thomas Rothvoß
482 Algorithms and Hardness for Subspace Approximation
Amit Deshpande, Madhur Tulsiani, and Nisheeth K. Vishnoi
497 Approximating Matrix p-norms
Aditya Bhaskara and Aravindan Vijayaraghavan
512 Subsampling Mathematical Relaxations and Average-case Complexity
Boaz Barak, Moritz Hardt, Thomas Holenstein, and David Steurer
532 Towards an SDP-based Approach to Spectral Methods: A Nearly-Linear-Time Algorithm for
Graph Partitioning and Decomposition
Lorenzo Orecchia and Nisheeth K. Vishnoi
546 Faster quantum algorithm for evaluating game trees
Ben W. Reichardt
560 Reflections for quantum query algorithms
Ben W. Reichardt
570 Temperature 1 Self-Assembly: Deterministic Assembly in 3D and Probabilistic Assembly in
2D
Matthew Cook, Yunhui Fu, and Robert Schweller
590 The Power of Nondeterminism in Self-Assembly
Nathaniel Bryans, Ehsan Chiniforooshan, David Doty, Lila Kari, and Shinnosuke Seki
603 Collapse
Günter Rote and Uri Zwick
614 Algorithms for Implicit Hitting Set Problems
Karthekeyan Chandrasekaran, Richard Karp, Erick Moreno-Centeno, and Santosh Vempala
630 An algorithmic decomposition of claw-free graphs leading to an O(n3)-algorithm for the
weighted stable set problem
Yuri Faenza, Gianpaolo Oriolo, and Gautier Stauffer
647 Randomized greedy: new variants of some classic approximation algorithms
Kevin P. Costello, Asaf Shapira, and Prasad Tetali
656 Randomized Variants of Johnson’s Algorithm for MAX SAT
Matthias Poloczek and Georg Schnitger
664 The Local Lemma is Tight for SAT
H. Gebauer, T. Szabó, and G. Tardos
675 Pricing on Paths: A PTAS for the Highway Problem
Fabrizio Grandoni and Thomas Rothvoß
685 On the Approximability of Budget Feasible Mechanisms
Ning Chen, Nick Gravin, and Pinyan Lu
700 Welfare Guarantees for Combinatorial Auctions with Item Bidding
Kshipra Bhawalkar and Tim Roughgarden
710 Mechanism Design via Correlation Gap
Qiqi Yan
720 Bayesian Incentive Compatibility via Fractional Assignments
Xiaohui Bei and Zhiyi Huang
734 Bayesian Incentive Compatibility via Matchings
Jason D. Hartline, Robert Kleinberg, and Azarakhsh Malekian
748 Bidimensionality and EPTAS
Fedor V. Fomin, Daniel Lokshtanov, Venkatesh Raman, and Saket Saurabh
760 Slightly Superexponential Parameterized Problems
Daniel Lokshtanov, Dániel Marx, and Saket Saurabh
777 Known Algorithms on Graphs on Bounded Treewidth are Probably Optimal
Daniel Lokshtanov, Dániel Marx, and Saket Saurabh
790 Continuous Local Search
Constantinos Daskalakis and Christos Papadimitriou
805 Range Selection and Median: Tight Cell Probe Lower Bounds and Adaptive Data Structures
Allan Grřnlund Jřrgensen and Kasper Green Larsen
Session 6 Invited Plenary Session
814 Where computer vision needs help from computer science
William T. Freeman
820 An Optimal-Time Construction of Sparse Euclidean Spanners with Tiny Diameter
Shay Solomon
840 Fast, precise and dynamic distance queries
Yair Bartal, Lee-Ad Gottlieb, Tsvi Kopelowitz, Moshe Lewenstein, and Liam Roditty
854 Approximate Nearest Neighbor Search for Low Dimensional Queries
Sariel Har-Peled and Nirman Kumar
868 Dimensionality reduction: Beyond the Johnson-Lindenstrauss bound
Yair Bartal, Ben Recht, and Leonard J. Schulman
888 A Nonlinear Approach to Dimension Reduction
Lee-Ad Gottlieb and Robert Krauthgamer
900 Hitting time results for Maker-Breaker games
Sonny Ben-Shimon, Asaf Ferber, Dan Hefetz, and Michael Krivelevich
913 Packing tight Hamilton cycles in 3-uniform hypergraphs
Alan Frieze, Michael Krivelevich, and Po-Shen Loh
933 Networks of random cycles
Colin Cooper, Martin Dyer, and Andrew J. Handley
945 Phase Transition for Glauber Dynamics for Independent Sets on Regular Trees
Ricardo Restrepo, Daniel Stefankovic, Juan C. Vera, Eric Vigoda, and Linjie Yang
957 On Belief Propagation Guided Decimation for Random k-SAT
Amin Coja-Oghlan
967 The Asymmetric Traveling Salesman Problem on Graphs with Bounded Genus
Shayan Oveis Gharan and Amin Saberi
976 Capacitated Metric Labeling
Matthew Andrews, Mohammad Taghi Hajiaghayi, Howard Karloff, and Ankur Moitra
996 Multicommodity Facility Location under Group Steiner Access Cost
Laura J. Poplawski and Rajmohan Rajaraman
1014 Survivable Network Design Problems in Wireless Networks
Debmalya Panigrahi
1028 Prize-collecting Steiner Problems on Planar Graphs
M. Bateni, C. Chekuri, A. Ene, M. T. Hajiaghayi, N. Korula, and D. Marx
1050 On Graph Crossing Number and Edge Planarization
Julia Chuzhoy, Yury Makarychev, and Anastasios Sidiropoulos
1070 Ranking with Submodular Valuations
Yossia Azar and Iftah Gamzu
1080 Multi-budgeted Matchings and Matroid Intersection via Dependent Rounding
Chandra Chekuri, Jan Vondrák, and Rico Zenklusen
1098 Submodular Maximization by Simulated Annealing
Shayan Oveis Gharan and Jan Vondrák
1117 The Matroid Median Problem
Ravishankar Krishnaswamy, Amit Kumar, Viswanath Nagarajan, Yogish Sabharwal, and Barna Saha
1131 Persistent Predecessor Search and Orthogonal point Location on the Word RAM
Timothy M. Chan
1146 New Approximation Algorithms for Minimum Enclosing Convex Shapes
Ankan Saha, S. V. N. Vishwanathan, and Xinhua Zhang
1161 Computing the Independence Number of Intersection Graphs
Jacob Fox and János Pach
1166 Minimum Cuts and Shortest Non-Separating Cycles via Homology Covers
Jeff Erickson and Amir Nayyeri
1177 Embedding Stacked Polytopes on a Polynomial-Size Grid
Erik D. Demaine and André Schulz
1188 Overlap properties of geometric expanders
Jacob Fox, Mikhail Gromov, Vincent Lafforgue, Assaf Naor, and János Pach
1198 On the Degree Distribution of Random Planar Graphs
Konstantinos Panagiotou and Angelika Steger
1211 Component structure of the vacant set induced by a random walk on a random graph
Colin Cooper and Alan Frieze
1222 The Multiple-Orientability Thresholds for Random Hypergraphs
Nikolaos Fountoulakis, Megha Khosla, and Konstantinos Panagioutou
1237 The Rigidity Transition in Random Graphs
Shiva Prasad Kasiviswanathan, Cristopher Moore, and Louis Theran
1253 Online Vertex-Weighted Bipartite Matching and Single-bid Budgeted Allocations
Gagan Aggarwal, Gagan Goel, Chinmay Karande, and Aranyak Mehta
1265 Secretary Problems: Laminar Matroid and Interval Scheduling
Sungjim Im and Yajun Wang
1275 Matroid Secretary Problem in the Random Assignment Model
José A. Soto
1285 Online Stochastic Matching: Online Actions Based on Offline Statistics
Vahideh H. Manshadi, Shayan Oveis Gharan, and Amin Saberi
1295 An Optimal Lower Bound for Buffer Management in Multi-Queue Switches
Marcin Bienkowski
1306 An Intersection Model for Multitolerance Graphs: Efficient Algorithms and Hierarchy
George B. Mertzios
1318 Faster and Dynamic Algorithms for Maximal End-Component Decomposition and Related
Graph Problems in Probabilistic Verification
Krishnendu Chatterjee and Monika Henzinger
1337 Faster Replacement Paths
Virginia Vassilevska Williams
1347 Computing Replacement Paths in Surface Embedded Graphs
Jeff Erickson and Amir Nayyeri
1355 Improved Dynamic Algorithms for Maintaining Approximate Shortest Paths Under
Deletions
Aaron Bernstein and Liam Roditty
1366 Algebraic Algorithms for Linear Matroid Parity Problems
Ho Yee Cheung, Lap Chi Lau, and Kai Man Leung
1383 On Parity Check (0, 1)-Matrix over Zp
Nader H. Bshouty and Hanna Mazzawi
1395 Code Equivalence and Group Isomorphism
László Babai, Paolo Codenotti, Joshua A. Grochow, and Youming Qiao
1409 Efficient algorithms for some special cases of the polynomial equivalence problem
Neeraj Kayal
1422 Low Rank Matrix-valued Chernoff Bounds and Approximate Matrix Multiplication
Avner Magen and Anastasios Zouzias
Session 10 Invited Plenary Session
1437 Computational Geometry for Non-Geometers: Recent Developments on Some Classical
Problems
Timothy Chan
1438 Improved Deterministic Algorithms for Decremental Transitive Closure and Strongly
Connected Components
Jakub Łącki
1446 Approximating the Girth
Liam Roddity and Roei Tov
1455 Approximating the Statistics of various Properties in Randomly Weighted Graphs
Yuval Emek, Amos Korman, and Yuval Shavitt
1468 Counting and detecting small subgraphs via equations and matrix multiplication
Miroslaw Kowaluk, Andrzej Lingas, and Eva-Marta Lundell
1477 On Succinct Convex Greedy Drawing of 3-Connected Plane Graphs
Xin He and Huaming Zhang
1487 Distributed Selfish Load Balancing on Networks
Petra Berenbrink, Martin Hoefer, and Thomas Sauerwald
1498 On the Complexity of Approximating a Nash Equilibrium
Constantinos Daskalakis
1518 Fast Convergence of Natural Bargaining Dynamics in Exchange Networks
Yashodhan Kanoria, Mohsen Bayati, Christian Borgs, Jennifer Chayes, and Andrea Montanari
1538 Wireless Capacity with Oblivious Power in General Metrics
Magnús M. Halldórsson and Pradipta Mitra
1549 A Constant-Factor Approximation for Wireless Capacity Maximization with Power Control
in the SINR Model
Thomas Kesselheim
1560 On LP-Based Approximability for Strict CSPs
Amit Kumar, Rajsekar Manokaran, Madhur Tulsiani, and Nisheeth K. Vishnoi
1574 Tight Bounds on the Approximability of Almost-satisfiable Horn SAT and Exact Hitting Set
Venkatesan Guruswami and Yuan Zhou
1590 Hardness Results for Agnostically Learning Low-Degree Polynomial Threshold Functions
Ilias Diakonikolas, Ryan O’Donnell, Rocco A. Servedio, and Yi Wu
1607 Tight Hardness Results for Minimizing Discrepancy
Moses Charikar, Alantha Newman, and Aleksandar Nikolov
1615 The complexity of finding independent sets in bounded degree (hyper)graphs of low
chromatic number
Venkatesan Guruswami and Ali Kemal Sinop
1627 Risk-Averse Stochastic Optimization: Probabilistically-Constrained Models and Algorithms
for Black-Box Distributions
Chaitanya Swamy
1647 Improved Approximation Results for Stochastic Knapsack Problems
Anand Bhalgat, Ashish Goel, and Sanjeev Khanna
1666 The stubborn problem is stubborn no more (a polynomial algorithm for 3-compatible
colouring and the stubborn list partition problem)
Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, and Jakub Onufry Wojtaszczyk
1675 Approximate Dynamic Programming using Halfspace Queries and Multiscale Monge
Decomposition
Gary L. Miller, Richard Peng, Russell Schwartz, and Charalampos Tsourakakis
1683 Nearly Tight Bounds for Testing Function Isomorphism
Sourav Chakraborty, David García-Soriano, and Arie Marsliah
1703 The Dichotomy of List Homomorphisms for Digraphs
Pavol Hell and Arash Rafiey
1714 Dichotomy for Holant* Problems of Boolean Domain
Jin-Yi Cai, Pinyan Lu, and Mingji Xia
1729 Bounding the Randomized Decision Tree Complexity of Read-Once Boolean Functions
Kazuyuki Amano
Session 12C
1745 Improved Space Bounds for Cache-Oblivious Range Reporting
Peyman Afshani and Norbert Zeh
1759 Triangulating the Square and Squaring the Triangle: Quadtrees and Delaunay
Triangulations are Equivalent
Maarten Löffler and Wolfgang Mulzer
1778 Improved Bound for the Union of Fat Triangles
Esther Ezra, Boris Aronov, and Micha Sharir
