SODA/ALENEX/ANALCO 2017 Schedule

January 15th, 2017

17:00-20:00 Registration and Welcome Reception (Las Arenas Foyer)

January 16th, 2017

8:00-17:00 Registration (Las Arenas Foyer)
9:00-10:00 Invited Talk 1 (Las Arenas Foyer)
Chair: Yair Bartal

9:00-10:00 A Dynamical View of Convex Optimization Algorithms
Benjamin Recht, University of California, Berkeley, USA
10:00-10:30 Coffee Break (Las Arenas Foyer)
10:30-12:30   ANALCO 1  (Saray)
Chair: Martin Dietzfelbinger

10:30-10:50   The Ordered and Colored Products in Analytic Combinatorics: Application to the Quantitative Study of Synchronizations in Concurrent Processes
Olivier Bodini, Matthieu Dien, Antoine Genitrini,Fr�d�ric Peschanski

10:55-11:15   On the cycle structure of the product of random maximal cycles
Mikl�s B�na, Boris Pittel

11:20-11:40   An Exact Enumeration of Distance-Hereditary Graphs
C�dric Chauve, �ric Fusy, J�r�mie Lumbroso

11:45-12:05   Isolated cycles of critical random graphs
Marc Noy, Vonjy Rasendrahasina, Vlady Ravelomanana,Juanjo Ru�

12:10-12:30   Cycle Basis Markov Chains for the Ising Model
Amanda Pascoe Streib, Noah Streib
10:30-12:30   SODA 1A  (Las Arenas II-IV)
Chair: Vahab Mirrokni

10:30-10:50   Proximity in the Age of Distraction: Robust Approximate Nearest Neighbor Search
Sariel Har-Peled,Sepideh Mahabadi

10:55-11:15   High-dimensional approximate r-nets
Georgia Avarikioti, Ioannis Z. Emiris, Loukas Kavouras,Ioannis Psarros

11:20-11:40   A Framework for Similarity Search with Space-Time Tradeoffs using Locality-Sensitive Filtering
Tobias Christiani

11:45-12:05   Optimal Hashing--based Time--Space Trade-offs for Approximate Near Neighbors
Alexandr Andoni, Thijs Laarhoven, Ilya Razenshteyn,Erik Waingarten

12:10-12:30   LSH Forest: Practical Algorithms Made Theoretical
Alexandr Andoni, Ilya Razenshteyn,Negev Shekel Nosatzki
10:30-12:30   SODA 1B  (Las Arenas I)
Chair: Anne Driemel

10:30-10:50   Faster approximation schemes for the two-dimensional knapsack problem
Sandy Heydrich,Andreas Wiese

10:55-11:15   Split Packing: An Algorithm for Packing Circles with Optimal Worst-Case Density
Sebastian Morr

11:20-11:40   Stochastic $k$-Center and $j$-Flat-Center Problems
Lingxiao Huang,Jian Li

11:45-12:05   Local search for max-sum diversification
Alfonso Cevallos, Friedrich Eisenbrand,Rico Zenklusen

12:10-12:30   Maximum Scatter TSP in Doubling Metrics
L�szl� Kozma,Tobias M�mke
10:30-12:30   SODA 1C  (Nelva)
Chair: Adi Ros�n

10:30-10:50   Matrix Balancing in $L_p$ Norms: Bounding the Convergence rate of Osborne's Iteration
Rafail Ostrovsky, Yuval Rabani,Arman Yousefi

10:55-11:15   Decidability of the Membership Problem for $2\times 2$ integer matrices
Igor Potapov,Pavel Semukhin

11:20-11:40   The Identity Problem for Matrix Semigroups in $\text{SL}_2(\mathbb{Z})$ is NP-complete
Paul C. Bell, Mika Hirvensalo,Igor Potapov

11:45-12:05   Exploring an Infinite Space with Finite Memory Scouts
Lihi Cohen, Yuval Emek, Oren Louidor,Jara Uitto

12:10-12:30   Universal Shape Replicators via Self-Assembly with Attractive and Repulsive Forces
Cameron Chalk, Erik D. Demaine, Martin L. Demaine, Eric Martinez, Robert Schweller, Luis Vega,Tim Wylie
12:30-14:00 Lunch (Nixe I-II / Spiral Restaurant)
14:00-15:00 Invited Talk 2 (Las Arenas II-IV)
Chair: Mikkel Thorup

14:00-15:00 Clique colouring random graphs
Colin McDiarmid, University of Oxford, United Kingdom
15:00-16:35   ANALCO 2  (Saray)
Chair: Hsien-Kuei Hwang

15:00-15:20   Iterative Cutting and Pruning of Planar Trees
Benjamin Hackl, Sara Kropf,Helmut Prodinger

15:25-15:45   On the distribution of random walk hitting times in random trees
Joubert Oosthuizen,Stephan Wagner

15:50-16:10   A note on the scaling limits of random P�lya trees
Bernhard Gittenberger, Emma Yu Jin,Michael Wallner

16:15-16:35   Rates of convergence for balanced irreducible two-color P�lya urns
Andrea Kuntschik,Ralph Neininger
15:00-16:35   SODA 2A  (Las Arenas II-IV)
Chair: Mikkel Thorup

15:00-15:20   Parameter-free Locality Sensitive Hashing for Spherical Range Reporting
Thomas D. Ahle, Martin Aum�ller,Rasmus Pagh

15:25-15:45   Distance Sensitive Bloom Filters Without False Negatives
Mayank Goswami, Rasmus Pagh, Francesco Silvestri,Johan Sivertsen

15:50-16:10   Optimal Approximate Polytope Membership
Sunil Arya, Guilherme D. da Fonseca,David M. Mount

16:15-16:35   Massively-Parallel Similarity Join, Edge-Isoperimetry, and Distance Correlations on the Hypercube
Paul Beame,Cyrus Rashtchian
15:00-16:35   SODA 2B  (Las Arenas I)
Chair: Nicole Megow

15:00-15:20   Even Delta-Matroids and the Complexity of Planar Boolean CSPs
Alexandr Kazda, Vladimir Kolmogorov,Michal Rol�nek

15:25-15:45   Linear Diophantine Equations, Group CSPs, and Graph Isomorphism
Christoph Berkholz,Martin Grohe

15:50-16:10   Robust algorithms with polynomial loss for near-unanimity CSPs
V�ctor Dalmau, Marcin Kozik, Adrei Krohkin, Konstantin Makarychev, Yury Makarychev,Jakub Opr�al

16:15-16:35   Parameterized Algorithms for Constraint Satisfaction Problems Above Average with Global Cardinality Constraints
Xue Chen,Yuan Zhou
15:00-16:35   SODA 2C  (Nelva)
Chair: Adi Ros�n

15:00-15:20   Hardness of Permutation Pattern Matching
V�t Jel�nek,Jan Kynčl

15:25-15:45   pBWT: Achieving Succinct Data Structures for Parameterized Pattern Matching and Related Problems
Arnab Ganguly, Rahul Shah,Sharma V. Thankachan

15:50-16:10   Space-Efficient Construction of Compressed Indexes in Deterministic Linear Time
Ian Munro, Gonzalo Navarro,Yakov Nekrich

16:15-16:35   Sparse Suffix Tree Construction in Optimal Time and Space
Paweł Gawrychowski,Tomasz Kociumaka
16:35-17:00 Coffee Break (Las Arenas Foyer)
17:00-18:35   ANALCO 3  (Saray)
Chair: Olivier Bodini

17:00-17:20   The recurrence function of a random Sturmian word
Pablo Rotondo,Brigitte Vall�e

17:25-17:45   An Extended Note on the Comparison-optimal Dual Pivot Quickselect
Daniel Krenn

17:50-18:10   External Profile of Symmetric Digital Search Trees
Michael Drmota, Michael Fuchs, Hsien-Kuei Hwang,Ralph Neininger

18:15-18:35   Partial Match Queries in Relaxed $K$-d$t$ trees
Amalia Duch,Gustavo Lau
17:00-19:00   SODA 3A  (Las Arenas II-IV)
Chair: Vijaya Ramachandran

17:00-17:20   Fully dynamic all-pairs shortest paths with worst-case update-time revisited
Ittai Abraham, Shiri Chechik,Sebastian Krinninger

17:25-17:45   Deterministic Partially Dynamic Single Source Shortest Paths for Sparse Graphs
Aaron Bernstein,Shiri Chechik

17:50-18:10   Fully Dynamic Approximate Maximum Matching and Minimum Vertex Cover in $O(\log^3 n)$ Worst Case Update Time
Sayan Bhattacharya, Monika Henzinger,Danupon Nanongkai

18:15-18:35   Connectivity Oracles for Graphs Subject to Vertex Failures
Ran Duan,Seth Pettie

18:40-19:00   Fully Dynamic Connectivity in $O(\log n(\log\log n)^2)$ Amortized Expected Time
Shang-En Huang, Dawei Huang, Tsvi Kopelowitz,Seth Pettie
17:00-19:00   SODA 3B  (Las Arenas I)
Chair: Matt Weinberg

17:00-17:20   Best-Response Dynamics in Combinatorial Auctions with Item Bidding
Paul D�tting,Thomas Kesselheim

17:25-17:45   Convergence of Incentive-Driven Dynamics in Fisher Markets
Krishnamurthy Dvijotham, Yuval Rabani,Leonard Schulman

17:50-18:10   Totally Unimodular Congestion Games
Alberto Del Pia, Michael Ferris,Carla Michini

18:15-18:35   Playing Anonymous Games using Simple Strategies
Yu Cheng, Ilias Diakonikolas,Alistair Stewart

18:40-19:00   Computing Walrasian Equilibria: Fast Algorithms and Structural Properties
Renato Paes Leme,Sam Chiu-wai Wong
17:00-19:00   SODA 3C  (Nelva)
Chair: Yair Bartal

17:00-17:20   Metric embeddings with outliers
Anastasios Sidiropoulos, Dingkang Wang,Yusu Wang

17:25-17:45   Probabilistic clustering of high dimensional norms
Assaf Naor

17:50-18:10   Near-Optimal (Euclidean) Metric Compression
Piotr Indyk,Tal Wagner

18:15-18:35   A Treehouse with Custom Windows: Minimum Distortion Embeddings into Bounded Treewidth Graphs
Amir Nayyeri,Benjamin Raichel

18:40-19:00   Beyond Metric Embedding: Approximating Group Steiner Trees on Bounded Treewidth Graphs
Parinya Chalermsook, Syamantak Das, Bundit Laekhanukit,Daniel Vaz
19:00-19:30 ANALCO/ALENEX Business Meeting (Las Arenas II-IV)

January 17th, 2017

9:00-17:00 Registration (Las Arenas Foyer)
9:00-10:00 Invited Talk 3 (Las Arenas Foyer)
Chair: Philip Klein

9:00-10:00 Systems and Algorithms for the Internet of Things
Dina Katabi, Massachusetts Institute of Technology, USA
10:00-10:30 Coffee Break (Las Arenas Foyer)
10:30-12:30   ANALCO 4  (Saray)
Chair: Robert Sedgewick

10:30-10:50   Multivariate CLT follows from strong Rayleigh property
Subhroshekhar Ghosh, Thomas M. Liggett,Robin Pemantle

10:55-11:15   Phase Transitions in Parameter Rich Optimization Problems
Joachim M. Buhmann, Julien Dumazert, Alexey Gronskiy,Wojciech Szpankowski

11:20-11:40   On Symmetries of Non-Plane Trees in a Non-Uniform Model
Jacek Cichoń, Abram Magner, Wojciech Szpankowski,Krzysztof Turowski

11:45-12:05   An analogue to Dixon's theorem for automaton groups
Thibault Godin

12:10-12:30   A Refined Analysis of LSH for Well-dispersed Data Points
Wenlong Mou,Liwei Wang
10:30-12:30   SODA 4A  (Las Arenas II-IV)
Chair: Vijaya Ramachandran

10:30-10:50   Negative-Weight Shortest Paths and Unit Capacity Minimum Cost Flow in $\tilde{O}(m^{10/7}\logW)$ Time
Michael B. Cohen, Aleksander Madry, Piotr Sankowski,Adrian Vladu

10:55-11:15   Generalized Preconditioning and Undirected Minimum-Cost Flow
Jonah Sherman

11:20-11:40   Scaling Algorithms for Weighted Matching in General Graphs
Ran Duan, Seth Pettie,Hsin-Hao Su

11:45-12:05   Near-Linear Time Approximation Schemes for Some Implicit Fractional Packing Problems
Chandra Chekuri,Kent Quanrud

12:10-12:30   Fast and Memory-Efficient Algorithms for Evacuation Problems
Miriam Schl�ter,Martin Skutella
10:30-12:30   SODA 4B  (Las Arenas I)
Chair: Maria Serna

10:30-10:50   Approximate Hierarchical Clustering via Sparsest Cut and Spreading Metrics
Moses Charikar,Vaggos Chatziafratis

10:55-11:15   Approximating Multicut and the demand graph
Chandra Chekuri,Vivek Madan

11:20-11:40   Minimum Fill-In: Inapproximability and Almost Tight Lower Bounds
Yixin Cao,R.B. Sandeep

11:45-12:05   Minimizing the Union: Tight Approximations for Small Set Bipartite Vertex Expansion
Eden Chlamt�č, Michael Dinitz,Yury Makarychev

12:10-12:30   Approximation Algorithms for Label Cover and The Log-Density Threshold
Eden Chlamt�č, Pasin Manurangsi, Dana Moshkovitz,Aravindan Vijayaraghavan
10:30-12:30   SODA 4C  (Nelva)
Chair: Matt Weinberg

10:30-10:50   An Axiomatic and an Average-Case Analysis of Algorithms and Heuristics for Metric Properties of Graphs
Michele Borassi, Pierluigi Crescenzi,Luca Trevisan

10:55-11:15   Find Your Place: Simple Distributed Algorithms for Community Detection
Luca Becchetti, Andrea Clementi, Emanuele Natale, Francesco Pasquale,Luca Trevisan

11:20-11:40   Sorting from Noisier Samples
Aviad Rubinstein,Shai Vardi

11:45-12:05   Sampling on the Sphere by Mutually Orthogonal Subspaces
Uri Grupel

12:10-12:30   Exponential Segregation in a Two-Dimensional Schelling Model with Tolerant Individuals
Nicole Immorlica, Robert Kleinberg, Brendan Lucier,Morteza Zadomighaddam
12:30-14:00 Lunch (Nixe I-II / Spiral Restaurant)
14:00-16:00   ALENEX 1  (Saray)
Chair: Vijaya Ramachandran

14:00-14:20   Distributed Graph-based Topology Adaptation using Motif Signatures
Michael Stein, Karsten Weihe, Augustin Wilberg, Roland Kluge, Julian M. Klomp, Mathias Schnee, Lin Wang,Max M�hlh�user

14:25-14:45   Indexing Variation Graphs
Jouni Sir�n

14:50-15:10   Engineering a direct k-way Hypergraph Partitioning Algorithm
Yaroslav Akhremtsev, Tobias Heuer, Peter Sanders,Sebastian Schlag

15:15-15:35   Computing Critical Nodes in Directed Graphs
Nilakantha Paudel, Loukas Georgiadis,Giuseppe F. Italiano

15:40-16:00   I/O-efficient Generation of Massive Graphs Following the LFR Benchmark
Michael Hamann, Ulrich Meyer, Manuel Penschuck,Dorothea Wagner
14:00-16:00   SODA 5A  (Las Arenas II-IV)
Chair: Adi Ros�n

14:00-14:20   Tight Bounds for Online TSP on the Line
Antje Bjelde, Yann Disser, Jan Hackfeld, Christoph Hansknecht, Maarten Lipmann, Julie Mei�ner, Kevin Schewior, Miriam Schl�ter,Leen Stougie

14:25-14:45   An Improved Upper Bound for the Universal TSP on the Grid
George Christodoulou,Alkmini Sgouritsa

14:50-15:10   The (h,k)-Server Problem on Bounded-Depth Trees
Nikhil Bansal, Marek Eli�, Grigorios Koumoutsos,&Lstroke;ukasz Jeż

15:15-15:35   Online Lower Bounds via Duality
Yossi Azar, Ilan Reuven Cohen,Alan Roytman

15:40-16:00   Polylogarithmic Bounds on the Competitiveness of Min-cost Perfect Matching with Delays
Yossi Azar, Ashish Chiplunkar,Haim Kaplan
14:00-16:00   SODA 5B  (Las Arenas I)
Chair: Shay Mozes

14:00-14:20   A Faster Pseudopolynomial Time Algorithm for Subset Sum
Konstantinos Koiliaris,Chao Xu

14:25-14:45   A Near-Linear Pseudopolynomial Time Algorithm for Subset Sum
Karl Bringmann

14:50-15:10   Computing minimum cuts in hypergraphs
Chandra Chekuri,Chao Xu

15:15-15:35   Random Contractions and Sampling for Hypergraph and Hedge Connectivity
Mohsen Ghaffari, David R. Karger,Debmalya Panigrahi

15:40-16:00   Sandpile prediction on a tree in near linear time
Akshay Ramachandran,Aaron Schild
14:00-16:00   SODA 5C  (Nelva)
Chair: Andrea Pietracaprina

14:00-14:20   Explicit Resilient Functions Matching Ajtai-Linial
Raghu Meka (talk given by Parikshit Gopalan)

14:25-14:45   Optimal induced universal graphs for bounded-degree graphs
Noga Alon,Rajko Nenadov

14:50-15:10   Approximation Algorithms for Finding Maximum Induced Expanders
Shayan Oveis Gharan,Alireza Rezaei

15:15-15:35   Parallel Algorithms and Concentration Bounds for the Lovasz Local Lemma via Witness-DAGs
Bernhard Haeupler,David G. Harris

15:40-16:00   Deterministic parallel algorithms for fooling polylogarithmic juntas and the Lov�sz Local Lemma
David G. Harris
16:00-16:25 Coffee Break (Las Arenas Foyer)
16:25-18:00   ALENEX 2  (Saray)
Chair: Subhash Suri

16:25-16:45   CSA++: Fast Pattern Search for Large Alphabets
Simon Gog, Alistair Moffat,Matthias Petri

16:50-17:10   Robust Massively Parallel Sorting
Michael Axtmann,Peter Sanders

17:15-17:35   Engineering External Memory Induced Suffix Sorting
Juha K�rkk�inen, Dominik Kempa, Simon J. Puglisi,Bella Zhukova

17:40-18:00   Compact Dynamic Rewritable (CDRW) Arrays
Andreas Poyias, Simon J. Puglisi,Rajeev Raman
16:25-18:00   SODA 6A  (Las Arenas II-IV)
Chair: Nicole Megow

16:25-16:45   Online Submodular Maximization with Free Disposal: Randomization Beats 1/4 for Partition Matroids
T.-H. Hubert Chan, Zhiyi Huang, Shaofeng H.-C. Jiang, Ning Kang,Zhihao Gavin Tang

16:50-17:10   Reordering Buffers with Logarithmic Diameter Dependency for Trees
Matthias Englert,Harald R�cke

17:15-17:35   $O(\mbox{depth})$-Competitive Algorithm for Online Multi-level Aggregation
Niv Buchbinder, Moran Feldman, Joseph Naor,Ohad Talmon

17:40-18:00   Competitive analysis of the top-K ranking problem
Xi Chen, Sivakanth Gopi, Jieming Mao,Jon Schneider
16:25-18:00   SODA 6B  (Las Arenas I)
Chair: Grigory Yaroslavtsev

16:25-16:45   Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimization
Vitaly Feldman, Crist�bal Guzm�n,Santosh Vempala

16:50-17:10   Sample Optimal Density Estimation in Nearly-Linear Time
Jayadev Acharya, Ilias Diakonikolas, Jerry Li,Ludwig Schmidt

17:15-17:35   On Rationality of Nonnegative Matrix Factorization
Dmitry Chistikov, Stefan Kiefer, Ines Maru�ić, Mahsa Shirmohammadi,James Worrell

17:40-18:00   Make Up Your Mind: The Price of Online Queries in Differential Privacy
Mark Bun, Thomas Steinke,Jonathan Ullman
16:25-18:00   SODA 6C  (Nelva)
Chair: Matt Weinberg

16:25-16:45   ETH Hardness for Densest-$k$-Subgraph with Perfect Completeness
Mark Braverman, Young Kun Ko, Aviad Rubinstein,Omri Weinstein

16:50-17:10   The Rainbow at the End of the Line - A PPAD Formulation of the Colorful Carath�odory Theorem with Applications
Fr�d�ric Meunier, Wolfgang Mulzer, Pauline Sarrabezolles,Yannik Stein

17:15-17:35   Hardness of Continuous Local Search: Query Complexity and Cryptographic Lower Bounds
Pavel Hub�ček,Eylon Yogev

17:40-18:00   LP Relaxations of Some NP-Hard Problems Are as Hard as Any LP
Daniel Prů�a,Tom� Werner
18:00-19:00 SODA Business Meeting (Las Arenas II-IV)
20:15-22:15 Banquet (Restaurant Mar�tim)

January 18th, 2017

9:00-12:30 Registration (Las Arenas Foyer)
9:00-9:20 Tribute to David Johnson (speech by Mihalis Yannakakis) (Las Arenas Foyer)
9:20-10:30   ALENEX 3  (Las Arenas Foyer)
Chair: Rajeev Raman

9:20-9:40   Engineering a Distributed Full-Text Index
Johannes Fischer, Florian Kurpicz,Peter Sanders

9:45-10:05   Elias-Fano meets Single-Term Top-k Document Retrieval
Julian Labeit,Simon Gog

10:10-10:30   Efficient Set Intersection Counting Algorithm for Text Similarity Measures
Preethi Lahoti, Patrick K. Nicholson,Bilyana Taneva
9:20-10:30   SODA 7A  (Las Arenas II-IV)
Chair: Philip Klein

9:20-9:40   Approximation and Kernelization for Chordal Vertex Deletion
Bart M.P. Jansen,Marcin Pilipczuk

9:20-9:40   Feedback Vertex Set Inspired Kernel for Chordal Vertex Deletion
Akanksha Agrawal, Daniel Lokshtanov, Pranabendu Misra, Saket Saurabh,Meirav Zehavi

9:45-10:05   Fully polynomial-time parameterized computations for graphs and matrices of low treewidth
Fedor V. Fomin, Daniel Lokshtanov, Michał Pilipczuk, Saket Saurabh,Marcin Wrochna

10:10-10:30   Spanning Circuits in Regular Matroids
Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov,Saket Saurabh
9:20-10:30   SODA 7B  (Las Arenas I)
Chair: Shay Mozes

9:20-9:40   Algorithmic and Hardness Results for the Hub Labeling Problem
Haris Angelidakis, Yury Makarychev,Vsevolod Oparin

9:45-10:05   Beyond Highway Dimension: Small Distance Labels Using Tree Skeletons
Adrian Kosowski,Laurent Viennot

10:10-10:30   $(1+\epsilon)$-Approximate f-Sensitive Distance Oracles
Shiri Chechik, Sarel Cohen, Amos Fiat,Haim Kaplan
9:20-10:30   SODA 7C  (Nelva)
Chair: Mikkel Thorup

9:20-9:40   On the insertion time of random walk cuckoo hashing
Alan Frieze,Tony Johansson

9:45-10:05   File Maintenance: When in Doubt, Change the Layout!
Michael Bender, Jeremy T. Fineman, Seth Gilbert, Tsvi Kopelowitz,Pablo Montes

10:10-10:30   Cross-Referenced Dictionaries and the Limits of Write Optimization
Peyman Afshani, Michael A. Bender, Mart�n Farach-Colton, Jeremy T. Fineman, Mayank Goswami,Meng-Tsung Tsai
10:30-10:55 Coffee Break (Las Arenas Foyer)
10:55-12:30   ALENEX 4  (Saray)
Chair: Baruch Schieber

10:55-11:15   The Moser-Tardos Resample algorithm: Where is the limit? (an experimental inquiry)
Jan Dean Catarata, Scott Corbett, Harry Stern, Mario Szegedy, Tomas Vyskocil,Zheng Zhang

11:20-11:40   Determining Tournament Payout Structures for Daily Fantasy Sports
Christopher Musco, Maxim Sviridenko,Justin Thaler

11:45-12:05   Map Simplification with Topology Constraints: Exactly and in Practice
Stefan Funke, Thomas Mendel, Alexander Miller, Sabine Storandt,Maria Wiebe

12:10-12:30   Asynchronous Column Generation
Saverio Basso,Alberto Ceselli
10:55-12:30   SODA 8A  (Las Arenas II-IV)
Chair: Grigory Yaroslavtsev

10:55-11:15   Testing for Forbidden Order Patterns in an Array
Ilan Newman, Yuri Rabinovich, Deepak Rajendraprasad,Christian Sohler

11:20-11:40   Sequential measurements, disturbance and property testing
Aram W. Harrow, Cedric Yen-Yu Lin,Ashley Montanaro

11:45-12:05   A tight bound for Green's arithmetic triangle removal lemma in vector spaces
L�szl� Mikl�s Lov�sz,Jacob Fox

12:10-12:30   Fast Permutation Property Testing
Jacob Fox,Fan Wei
10:55-12:30   SODA 8B  (Las Arenas I)
Chair: Mikkel Thorup

10:55-11:15   Polynomial Kernels and Wideness Properties of Nowhere Dense Graph Classes
Stephan Kreutzer, Roman Rabinovich,Sebastian Siebertz

11:20-11:40   Partitioning a Graph into Small Pieces with Applications to Path Transversal
Euiwoong Lee

11:45-12:05   LP-branching algorithms based on biased graphs
Magnus Wahlstr�m

12:10-12:30   About the Structure of the Integer Cone and its Application to Bin Packing
Klaus Jansen,Kim-Manuel Klein
10:55-12:30   SODA 8C  (Nelva)
Chair: Andrea Pietracaprina

10:55-11:15   Online and Random-order Load Balancing Simultaneously
Marco Molinaro

11:20-11:40   Building a Good Team: Secretary Problems and the Supermodular Degree
Moran Feldman,Rani Izsak

11:45-12:05   Combinatorial Prophet Inequalities
Aviad Rubinstein,Sahil Singla

12:10-12:30   Adaptivity Gaps for Stochastic Probing: Submodular and XOS Functions
Anupam Gupta, Viswanath Nagarajan,Sahil Singla
12:30-14:00 Lunch (Nixe I-II / Spiral Restaurant)
14:00-16:00   ALENEX 5  (Saray)
Chair: S�ndor Fekete

14:00-14:20   Parallel $d$-D Delaunay Triangulations in Shared and Distributed Memory
Daniel Funke,Peter Sanders

14:25-14:45   An Efficient Algorithm for the 1D Total Visibility-Index Problem
Peyman Afshani, Mark de Berg, Henri Casanova, Benjamin Karsin, Colin Lambrechts, Nodari Sitchinava,Constantinos Tsirogiannis

14:50-15:10   Computing the Expected Value and Variance of Geometric Measures
Frank Staals,Constantinos Tsirogiannis

15:15-15:35   Growing Balls in $\mathbb{R}^d$
Daniel Bahrdt, Michael Becher, Stefan Funke, Filip Krumpe, Andre Nusser, Martin Seybold,Sabine Storandt

15:40-16:00   I/O-Efficient Event Based Depression Flood Risk
Lars Arge, Mathias Rav, Sarfraz Raza,Morten Revsb�k
14:00-16:00   SODA 9A  (Las Arenas II-IV)
Chair: Vahab Mirrokni

14:00-14:20   $(1+\Omega(1))$-Approximation to MAX-CUT Requires Linear Space
Michael Kapralov, Sanjeev Khanna, Madhu Sudan,Ameya Velingker

14:25-14:45   On Estimating Maximum Matching Size in Graph Streams
Sepehr Assadi, Sanjeev Khanna,Yang Li

14:50-15:10   Faster Sublinear Algorithms via Conditional Sampling
Themistoklis Gouleakis, Christos Tzamos,Manolis Zampetakis

15:15-15:35   Input Sparsity Time Low-Rank Approximation via Ridge Leverage Score Sampling
Michael B. Cohen, Cameron Musco,Christopher Musco

15:40-16:00   A Hybrid Sampling Scheme for Triangle Counting
John Kallaugher,Eric Price
14:00-16:00   SODA 9B  (Las Arenas I)
Chair: Maria Serna

14:00-14:20   An FPTAS for Counting Proper Four-Colorings on Cubic Graphs
Pinyan Lu, Kuan Yang, Chihao Zhang,Minshen Zhu

14:25-14:45   Random cluster dynamics for the Ising model is rapidly mixing
Heng Guo,Mark Jerrum

14:50-15:10   Approximately Sampling Elements with Fixed Rank in Graded Posets
Prateek Bhakta, Ben Cousins, Matthew Fahrbach,Dana Randall

15:15-15:35   Random walks with the minimum degree local rule have $O(n^2)$ cover time
Roee David,Uriel Feige

15:40-16:00   Random Walks and Evolving Sets: Faster Convergences and Limitations
Siu On Chan, Tsz Chiu Kwok,Lap Chi Lau
14:00-16:00   SODA 9C  (Nelva)
Chair: Andrea Pietracaprina

14:00-14:20   An $O(nm)$ time algorithm for finding the min length directed cycle in a graph
James B. Orlin,Antonio Sede�o-Noda

14:25-14:45   Strong Connectivity in Directed Graphs under Failures, with Applications
Loukas Georgiadis, Giuseppe F. Italiano,Nikos Parotsidis

14:50-15:10   Faster Algorithms for Computing Maximal 2-Connected Subgraphs in Sparse Directed Graphs
Shiri Chechik, Thomas Dueholm Hansen, Giuseppe F. Italiano, Veronika Loitzenbauer,Nikos Parotsidis

15:15-15:35   Local Flow Partitioning for Faster Edge Connectivity
Monika Henzinger, Satish Rao,Di Wang

15:40-16:00   Doubly Balanced Connected Graph Partitioning
Saleh Soltan, Mihalis Yannakakis,Gil Zussman
16:00-16:25 Coffee Break (Las Arenas Foyer)
16:25-18:00   SODA 10A  (Las Arenas II-IV)
Chair: Philip Klein

16:25-16:45   Three Colors Suffice: Conflict-Free Coloring of Planar Graphs
Zachary Abel, Victor Alvarez, Erik D. Demaine, S�ndor P. Fekete, Aman Gour, Adam Hesterberg, Phillip Keldenich,Christian Scheffer

16:50-17:10   LP-Based Robust Algorithms for Noisy Minor-Free and Bounded Treewidth Graphs
Nikhil Bansal, Daniel Reichman,Seeun William Umboh

17:15-17:35   LR-Drawings of Ordered Rooted Binary Trees and Near-Linear Area Drawings of Outerplanar Graphs
Fabrizio Frati, Maurizio Patrignani,Vincenzo Roselli

17:40-18:00   Partial and Constrained Level Planarity
Guido Br�ckner,Ignaz Rutter
16:25-18:00   SODA 10B  (Las Arenas I)
Chair: Grigory Yaroslavtsev

16:25-16:45   Accurate and Nearly Optimal Sublinear Approximations to Ulam Distance
Timothy Naumovitz, Michael Saks,C. Ceshadhri

16:50-17:10   A framework for analyzing resparsification algorithms
Rasmus Kyng, Jakub Pachocki, Richard Peng,Sushant Sachdeva

17:15-17:35   Adaptive Matrix Vector Product
Santosh Vempala,David P. Woodruff

17:40-18:00   Low-Rank PSD Approximation in Input-Sparsity Time
Kenneth L. Clarkson,David P. Woodruff
16:25-18:00   SODA 10C  (Nelva)
Chair: Gerth St�lting Brodal

16:25-16:45   Locally testable and locally correctable codes approaching the Gilbert-Varshamov bound
Sivakanth Gopi, Swastik Kopparty, Rafael Oliveira, Noga Ron-Zewi,Shubhangi Saraf

16:50-17:10   Maximally Recoverable Codes for Grid-like Topologies
Parikshit Gopalan, Guangda Hu, Swastik Kopparty, Shubhangi Saraf, Carol Wang,Sergey Yekhanin

17:15-17:35   MDS Code Constructions with Small Sub-packetization and Near-optimal Repair Bandwidth
Venkatesan Guruswami,Ankit Singh Rawat

17:40-18:00   Bridging the Capacity Gap Between Interactive and One-Way Communication
Bernhard Haeupler,Ameya Velingker
18:00-18:45   SODA Awards  (Las Arenas II-IV)
Chair: Philip Klein

18:00-18:20   Subquadratic Algorithms for the Diameter and the Sum of Pairwise Distances in Planar Graphs
Sergio Cabello

18:25-18:45   A $(2+\epsilon)$-Approximation for Maximum Weight Matching in the Semi-Streaming Model
Ami Paz,Gregory Schwartzman

January 19th, 2017

9:00-10:00 Invited Talk 4 (Las Arenas II-IV)
Chair: Grigory Yaroslavtsev

9:00-10:00 Uncertainty and Optimization
Nikhil Bansal, Eindhoven University of Technology, The Netherlands
10:00-10:30 Coffee Break (Las Arenas Foyer)
10:30-12:30   SODA 11A  (Las Arenas II-IV)
Chair: Grigory Yaroslavtsev

10:30-10:50   Completeness for First-Order Properties on Sparse Structures with Algorithmic Applications
Jiawei Gao, Russell Impagliazzo, Antonina Kolokolova,Ryan Williams

10:55-11:15   Faster Online Matrix-Vector Multiplication
Kasper Green Larsen,Ryan Williams

11:20-11:40   Beating Brute Force for Systems of Polynomial Equations over Finite Fields
Daniel Lokshtanov, Ramamohan Paturi, Suguru Tamaki, Ryan Williams,Huacheng Yu

11:45-12:05   The Complexity of Simulation and Matrix Multiplication
Massimo Cairo,Romeo Rizzi

12:10-12:30   Better Approximations for Tree Sparsity in Nearly-Linear Time
Arturs Backurs, Piotr Indyk,Ludwig Schmidt
10:30-12:30   SODA 11B  (Las Arenas I)
Chair: Neal Young

10:30-10:50   Counting matchings in irregular bipartite graphs and random lifts
Marc Lelarge

10:55-11:15   A constant-time algorithm for middle levels Gray codes
Torsten M�tze,Jerri Nummenpalo

11:20-11:40   On Max-Clique for intersection graphs of sets and the Hadwiger-Debrunner numbers
Chaya Keller, Shakhar Smorodinky,G�bor Tardos

11:45-12:05   Core congestion is inherent in hyperbolic networks
Victor Chepoi, Feodor Dragan,Yann Vax�s

12:10-12:30   Better upper bounds on the F�redi-Hajnal limits of permutations
Josef Cibulka,Jan Kynčl
10:30-12:30   SODA 11C  (Nelva)
Chair: Shay Mozes

10:30-10:50   Popularity, Mixed Matchings, and Self-Duality
Chien-Chung Huang,Telikepalli Kavitha

10:55-11:15   Constant Approximation Algorithm for Non-Uniform Capacitated Multi-Item Lot-Sizing via Strong Covering Inequalities
Shi Li (talk given by Mateusz Lewandowski)

11:20-11:40   Small Extended Formulation for Knapsack Cover Inequalities from Monotone Circuits
Abbas Bazzi, Samuel Fiorini, Sangxia Huang,Ola Svensson

11:45-12:05   Extension Complexity Lower Bounds for Mixed-Integer Extended Formulations
Robert Hildebrand, Robert Weismantel,Rico Zenklusen

12:10-12:30   Opting Into Optimal Matchings
Avrim Blum, Ioannis Caragiannis, Nika Haghtalab, Ariel D. Procaccia, Eviatar B. Procaccia,Rohit Vaish
12:30-14:00 Lunch (Las Arenas Foyer)
14:00-16:00   SODA 12A  (Las Arenas II-IV)
Chair: Neal Young

14:00-14:20   Firefighting on Trees Beyond Integrality Gaps
David Adjiashvili, Andrea Baggio,Rico Zenklusen

14:25-14:45   Beating Approximation Factor Two for Weighted Tree Augmentation with Bounded Costs
David Adjiashvili

14:50-15:10   Simplex Transformations and the Multiway Cut Problem
Niv Buchbinder, Roy Schwartz,Baruch Weizman

15:15-15:35   To Augment or Not to Augment: Solving Unsplittable Flow on a Path by Creating Slack
Fabrizio Grandoni, Tobias M�mke, Andreas Wiese,Hang Zhou

15:40-16:00   Optimization of Bootstrapping in Circuits
Fabrice Benhamouda, Tancr�de Lepoint, Claire Mathieu,Hang Zhou
14:00-16:00   SODA 12B  (Las Arenas I)
Chair: Anne Driemel

14:00-14:20   Geodesic Spanners for Points on a Polyhedral Terrain
Mohammad Ali Abam, Mark de Berg,Mohammad Javad Rezaei Seraji

14:25-14:45   Computing the Fr�chet Distance between Real-Valued Surfaces
Bettina Speckmann, Kevin Buchin,Tim Ophelders

14:50-15:10   Incidences with curves and surfaces in three dimensions, with applications to distinct and repeated distances
Micha Sharir,Noam Solomon

15:15-15:35   Eliminating Depth Cycles among Triangles in Three Dimensions
Boris Aronov, Edward Y. Miller,Micha Sharir

15:40-16:00   Dynamic Planar Voronoi Diagrams for General Distance Functions and their Algorithmic Applications
Haim Kaplan, Wolfgang Mulzer, Liam Roditty, Paul Seiferth,Micha Sharir
14:00-16:00   SODA 12C  (Nelva)
Chair: Maria Serna

14:00-14:20   Distributed Degree Splitting, Edge Coloring, and Orientations
Mohsen Ghaffari,Hsin-Hao Su

14:25-14:45   Tight Network Topology Dependent Bounds on Rounds of Communication
Arkadev Chattopadhyay, Michael Langberg, Shi Li,Atri Rudra

14:50-15:10   Minimizing Message Size in Stochastic Communication Patterns: Fast Self-Stabilizing Protocols with 3 bits
Lucas Boczkowski, Amos Korman,Emanuele Natale

15:15-15:35   Time-space Trade-offs in Population Protocols
Dan Alistarh, James Aspnes, David Eisenstat, Rati Gelashvili,Ronald L. Rivest

15:40-16:00   Fair Coin Flipping: Tighter Analysis and the Many-Party Case
Niv Buchbinder, Iftach Haitner, Nissan Levi,Eliad Tsfadia
16:00-16:30 Coffee Break (Las Arenas Foyer)
16:30-18:30   SODA 13A  (Las Arenas II-IV)
Chair: Vahab Mirrokni

16:30-16:50   Fair Scheduling via Iterative Quasi-Uniform Sampling
Sungjin Im,Benjamin Moseley

16:55-17:15   A Logarithmic Additive Integrality Gap for Bin Packing
Rebecca Hoberg,Thomas Rothvoss

17:20-17:40   Iterative Partial Rounding for Vertex Cover with Hard Capacities
Mong-Jen Kao

17:20-17:40   Tight Algorithms for Vertex Cover with Hard Capacities on Multigraphs and Hypergraphs
Sam Chiu-wai Wong

17:45-18:05   Unrelated Machine Scheduling of Jobs with Uniform Smith Ratios
Christos Kalaitzis, Ola Svensson,Jakub Tarnawski

18:10-18:30   On the Configuration-LP of the Restricted Assignment Problem
Klaus Jansen,Lars Rohwedder
16:30-18:30   SODA 13B  (Las Arenas I)
Chair: Neal Young

16:30-16:50   Approximating Spanners and Directed Steiner Forest: Upper and Lower Bounds
Eden Chlamt�č, Michael Dinitz, Guy Kortsarz,Bundit Laekhanukit

16:55-17:15   A Hierarchy of Lower Bounds for Sublinear Additive Spanners
Amir Abboud, Greg Bodwin,Seth Pettie

17:20-17:40   LAST but not Least: Buy-at-Bulk via Online Spanners
Anupam Gupta, R. Ravi, Kunal Talwar,Seeun William Umboh

17:45-18:05   Linear Size Distance Preservers
Greg Bodwin

18:10-18:30   Efficient Algorithms for Constructing Very Sparse Spanners and Emulators
Michael Elkin,Ofer Neiman
16:30-18:30   SODA 13C  (Nelva)
Chair: Anne Driemel

16:30-16:50   When and Why the Topological Coverage Criterion Works
Nicholas J. Cavanna, Kirk P. Gardner,Donald R. Sheehy

16:55-17:15   Deciding Contractibility of a Non-Simple Curve on the Boundary of a 3-Manifold
�ric Colin de Verdi�re,Salman Parsa

17:20-17:40   An Efficient Representation for Filtrations of Simplicial Complexes
Jean-Daniel Boissonnat,Karthik C. S.

17:45-18:05   A polynomial time algorithm to compute quantum invariants of 3-manifolds with bounded first Betti number
Cl�ment Maria,Jonathan Spreer

18:10-18:30   Parameter-free Topology Inference and Sparsification for Data on Manifolds
Tamal Dey, Zhe Dong,Yusu Wang