Vrije Universiteit Amsterdam, June 4-6, 2018


All talks take place in the Auditorium, except where otherwise indicated (the parallel contributed talks sessions).

Click on a talk for abstracts or other information.

Monday, June 4

8:15 — 8:45 Registration (with coffee)
8:45 — 9:00 Welcome
9:00 — 10:00
Danupon Nanongkai — Dynamic graph algorithms and complexity

In this talk I will attempt to answer the following questions I have been asked quite often: What are the current challenges in dynamic graph algorithms? What are good starting points for PhD students and experienced researchers from other fields, who want to try working in this field? The talk will focus on challenges for basic graph problems (e.g. connectivity, shortest paths, maximum matching), and will survey some existing upper and lower bound results and techniques.

10:00 — 10:30
Aaron Bernstein — Online Bipartite Matching with Amortized O(log2 n) Replacements

Appeared in SODA 2018; coauthored with Jacob Holm and Eva Rotenberg. Search for paper

10:30 — 11:00 Coffee break
11:00 — 11:30
Anindya De — Trace Reconstruction with exp(O(n1/3)) Samples + Optimal Mean-based Algorithms for Trace Reconstruction

Appeared in STOC 2017; coauthored with (Independent works) Fedor Nazarov and Yuval Peres + Anindya De, Ryan O'Donnell and Rocco A. Servedio. Search for paper

11:30 — 12:00
Tselil Schramm — The Power of Sum-of-Squares for Detecting Hidden Structures

Appeared in FOCS 2017; coauthored with Samuel B. Hopkins, Pravesh K. Kothari, Aaron Potechin, Prasad Raghavendra and David Steurer. Search for paper

12:00 — 12:30
Uri Stemmer — Practical Locally Private Heavy Hitters

Appeared in NIPS 2017; coauthored with Raef Bassily, Kobbi Nissim and Abhradeep Thakurta. Search for paper

12:30 — 14:00 Lunch (provided)
14:00 — 15:30 Contributed talks 1 (sessions A & B in parallel)
15:30 — 16:00 Coffee break
16:00 — 17:00
Barna Saha — Space & time efficient algorithms for Lipschitz problems

Many fundamental sequence problems exhibit lipschitz property, that is whenever the input changes slightly, the change in the output is also bounded. Some examples include the longest increasing subsequence problem (studied since Schensted, 1961), the string edit distance computation (studied since Levenshtein, 1965), the language edit distance problem (studied since Aho and Peterson, 1972), RNA Folding (studied since Jacobson and Nussinov, 1980) etc. For all these problems, there exist simple polynomial time algorithms based on dynamic programming.

Dynamic programming is one of the most systematic ways of developing polynomial time algorithms, but it often suffers from high space and time complexity. In this talk, I will show a simple technique of amnesic dynamic programming using which we can improve either on time or space complexity of lipschitz problems allowing for additive approximations. For some of these problems, it is also possible to design an exact algorithm that runs faster than the corresponding dynamic programming using a reduction to lipschitz (min,+)-matrix multiplication. Time permitting, I will discuss how this raises serious doubts to the All Pairs Shortest Path conjecture which is the cornerstone to show cubic-hardness of a large collection of fundamental graph and matrix problems.

17:00 — 17:30
Sergio Cabello — Subquadratic Algorithms for the Diameter and the Sum of Pairwise Distances in Planar Graphs

Appeared in SODA 2017. Search for paper

17:30 — 18:00
Aviad Rubinstein — Distributed PCP Theorems for Hardness of Approximation in P

Appeared in FOCS 2017; coauthored with Amir Abboud and Ryan Williams. Search for paper

18:00 — 19:00 Poster session 1

Tuesday, June 5

9:00 — 10:00
Fabian Kuhn — On the Role of Randomization in Local Distributed Algorithms

Many modern computing systems are distributed and built in a decentralized way on top of large networks. As one of the key challenges when running a distributed algorithm in a large network, typically no node can know the state of the whole network and each node thus each node has to base its decisions on only partial, mostly local information about the network. The major goal of the research on local distributed algorithms is to understand to what extent nodes in a network can achieve a global goal such as solving some graph problem, based on only local information.

In my talk, I will focus on the role of using randomization in local distributed graph algorithms. In many cases, there currently is a large gap between the best randomized and deterministic algorithms and understanding whether this gap is inherent, is considered to be one of the central open questions of the area. I will discuss recent results that shed some light on what randomness is really needed for and that also allow to identify simple and basic problems that are complete for the class of problems that have efficient randomized distributed algorithms and for which we do not know efficient deterministic algorithms.

10:00 — 10:30
Seth Pettie — A Time Hierarchy Theorem for the LOCAL Model

Appeared in FOCS 2017; coauthored with Yi-Jun Chang. Search for paper

10:30 — 11:00 Coffee break
11:00 — 12:00
Ankur Moitra — Robustness Meets Algorithms

In every corner of machine learning and statistics, there is a need for estimators that work not just in an idealized model but even when their assumptions are violated. It turns out that being provably robust and being efficiently computable are often at odds with each other. In even the most basic settings such as robustly computing the mean and covariance, until recently the only known estimators were either hard to compute or could only tolerate a negligible fraction of errors in high-dimensional applications.

In this talk, we will survey the exciting recent progress in algorithmic robust statistics. We will give the first provably robust and efficiently computable estimators for several fundamental questions that were thought to be hard, and explain the main insights behind them. We will give practical applications to exploratory data analysis, and end with some open questions.

12:00 — 12:30
Moses Charikar — A Hitting Time Analysis of Stochastic Gradient Langevin Dynamics

Appeared in COLT 2017; coauthored with Yuchen Zhang and Percy Liang. Search for paper

12:30 — 14:00 Lunch (provided)
14:00 — 15:30 Contributed talks 2 (sessions A & B in parallel)
15:30 — 16:00 Coffee break
16:00 — 16:30
Vera Traub — Approaching 3/2 for the s-t-path TSP

Appeared in SODA 2018; coauthored with Jens Vygen. Search for paper

16:30 — 17:00
Chandra Chekuri — Approximating the Held-Karp Bound for Metric TSP in Nearly-Linear Time

Appeared in FOCS 2017; coauthored with Kent Quanrud. Search for paper

17:00 — 17:30
Parinya Chalermsook — From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More

Appeared in FOCS 2017; coauthored with Marek Cygan, Guy Kortsarz, Bundit Laekhanukit, Pasin Manurangsi, Danupon Nanongkai and Luca Trevisan. Search for paper

17:30 — 18:00
Pasin Manurangsi — Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph

Appeared in STOC 2017. Search for paper

18:00 — 19:00 Poster session 2
19:00 — 20:00 Business meeting (Rm 2A-00)

Wednesday, June 6

9:00 — 9:30
Rotem Oshman — A Rounds vs. Communication Tradeoff for Multi-Party Set Disjointness

Appeared in FOCS 2017; coauthored with Mark Braverman. Search for paper

9:30 — 10:00
Krzysztof Nowicki — MST in O(1) Round of Congested Clique

Appeared in SODA 2018; coauthored with Tomasz Jurdzinski. Search for paper

10:00 — 10:30
Magnús Halldorsson — Universal Framework for Wireless Scheduling Problems

Appeared in ICALP 2017; coauthored with Eyjólfur I. Ásgeirsson and Tigran Tonoyan. Search for paper

10:30 — 11:00 Coffee break
11:00 — 12:00
Jelani Nelson — Recent advances concerning the Johnson-Lindenstrauss lemma

A cornerstone result in the area of dimensionality reduction is the “Johnson-Lindenstrauss (JL) lemma”, which states that any n-point subset of Euclidean space embeds into m-dimensional Euclidean space for m = O((log n)/ε²) while preserving all pairwise distances multiplicatively up to 1+ε. Such embeddings are important in the design of algorithms, as high-dimensional data can be mapped to much lower dimension in a pre-processing stage so that subsequent algorithms run more efficiently. We will cover recent advances concerning the JL lemma and related topics.

12:00 — 12:30
Sanjeev Khanna — Randomized composable coresets for matching and vertex cover

Appeared in SPAA 2017; coauthored with Sepehr Assadi. Search for paper

12:30 — 14:00 Lunch (provided)
14:00 — 15:00
Timothy Chan — Geometric problems in moderate dimensions

Traditionally, algorithms in computational geometry are designed for low-dimensional instances, and running times tend to grow exponentially in the dimension. In this talk, we will look at some basic geometric problems, including orthogonal range search and Hamming nearest neighbor search, and survey recent algorithms that give nontrivial results even when the dimension goes beyond logarithmic. These results are of interest even to non-geometers, with connections to other fundamental problems such as APSP, OV, and SAT. Two classes of techniques will be explored: (i) new variations of standard geometric data structures like k-d trees and range trees, and (ii) the polynomial method.

15:00 — 15:30
Yuval Filmus — Twenty (Simple) Questions

Appeared in STOC 2017; coauthored with Yuval Dagan, Ariel Gabon and Shay Moran. Search for paper

15:30 — 16:00 Coffee break
16:00 — 16:30
Inbal Talgam-Cohen — Approximate modularity revisited

Appeared in STOC 2017; coauthored with Uriel Feige and Michal Feldman. Search for paper

16:30 — 17:00
Jonathan Kelner — Almost-Linear-Time Algorithms for Markov Chains and New Spectral Primitives for Directed Graphs

Appeared in STOC 2017; coauthored with Michael B. Cohen, John Peebles, Richard Peng, Anup B. Rao, Aaron Sidford and Adrian Vladu. Search for paper

17:00 — 17:30
Nikhil Bansal — Faster Space-Efficient Algorithms for Subset Sum and k-Sum

Appeared in STOC 2017; coauthored with Shashwat Garg, Jesper Nederlof and Nikhil Vyas. Search for paper

Accepted contributed presentations

Each contributed presentation will consist of a 5 minute talk, and on the same day, a poster presentation in the evening.

Monday 14:00 — 15:30, Session A (Auditorium)

14:00 Parinya Chalermsook, Syamantak Das, Guy Even, Bundit Laekhanukit and Daniel Vaz — Survivable Network Design for Group Connectivity in Low-Treewidth Graphs
Roee David, Karthik C.S. and Bundit Laekhanukit — On the Complexity of Closest Pair via Polar-Pair of Point-Sets
Pavel Kolev, Karl Bringmann and David Woodruff — Approximation Algorithms for ℓ0-Low Rank Approximation
Jarosław Byrka, Krzysztof Sornat and Joachim Spoerhase — Constant-Factor Approximation for Ordered k-Median
Mark de Berg, Hans L. Bodlaender, Sándor Kisfaludi-Bak, Dániel Marx and Tom van der Zanden — A Framework for ETH-tight Algorithms and Lower Bounds in Geometric Intersection Graphs
14:30 Matthias Rost and Stefan Schmid — Approximate Graph Embeddings in the Cloud
Rajesh Chitnis, Andreas Emil Feldmann and Pasin Manurangsi — Parameterized Approximation Algorithms for Bidirected Steiner Network Problems
Buddhima Gamlath, Sangxia Huang and Ola Svensson — Semi-Supervised Algorithms for Approximately Optimal and Accurate Clustering
Antonios Antoniadis, Krzysztof Fleszar, Ruben Hoeksma and Kevin Schewior — A PTAS for Euclidean TSP with Hyperplane Neighborhoods
Waldo Gálvez, Fabrizio Grandoni, Salvatore Ingala, Arindam Khan, Sandy Heydrich and Andreas Wiese — Approximating Geometric Knapsack via L-packings
15:00 Pavel Dvořák, Andreas Emil Feldmann, Dušan Knop, Tomáš Masařík, Tomáš Toufar and Pavel Veselý — Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices
Fabrizio Grandoni, Christos Kalaitzis and Rico Zenklusen — Improved Approximation for Tree Augmentation: Saving by Rewiring
Ohad Trabelsi — Nearly Optimal Time Bounds for kPath in Hypergraphs
Markus Brill, Till Fluschnik, Vincent Froese, Brijnesh Johannes Jain, Rolf Niedermeier and David Schultz — Exact Mean Computation in Dynamic Time Warping Spaces
Dominik Kempa and Nicola Prezza — String Attractors: a Unifying Theory of Repetitiveness

Monday 14:00 — 15:30, Session B (Rm 5A-00)

14:00 Gramoz Goranci, Monika Henzinger and Pan Peng — The Power of Vertex Sparsifiers in Dynamic Graph Algorithms
Jacob Holm, Eva Rotenberg and Mikkel Thorup — Dynamic Bridge-Finding in Õ(log2 n) Amortized Time
Danupon Nanongkai, Thatchaphol Saranurak and Christian Wulff-Nilsen — Dynamic Minimum Spanning Forest with Subpolynomial Worst-case Update Time
Fabrizio Grandoni, Anupam Gupta, Stefano Leonardi, Piotr Sankowski and Chris Schwiegelshohn — (1 + ε)-Approximate Incremental Matchings in Linear Time
Gopal Pandurangan, Peter Robinson and Michele Scquizzato — A Time- and Message-Optimal Distributed Algorithm for Minimum Spanning Trees
14:30 Adrian Kosowski and Przemysław Uznański — Population protocols made easy
Darya Melnyk, Yuyi Wang and Roger Wattenhofer — Byzantine Preferential Voting
Alkida Balliu, Juho Hirvonen, Janne H. Korhonen, Tuomo Lempiäinen, Dennis Olivetti and Jukka Suomela — New Classes of Distributed Time Complexity
Ami Paz — Quadratic and Near-Quadratic Lower Bounds for Distributed Graph Algorithms
Laurent Feuilloley and Pierre Fraigniaud — Error-Sensitive Proof-Labeling Schemes
15:00 Joshua Daymude, Robert Gmyr, Kristian Hinnenthal, Irina Kostitsyna, Fabian Kuhn, Andréa Richa, Dorian Rudolph, Christian Scheideler and Thim Strothmann — Towards hybrid programmable matter: shape recognition, detection, and sealing algorithms for finite automaton robots
Ivor Hoog V.D., Elena Khramtcova and Maarten Loffler — Dynamic Smooth Compressed Quadtrees
Daniel Dadush and Sophie uiberts — A Friendly Smoothed Analysis of the Simplex Method
Krishnendu Chatterjee, Wolfgang Dvořák, Monika Henzinger and Veronika Loitzenbauer — Lower Bounds for Symbolic Computation on Graphs: Strongly Connected Components, Liveness, Safety, and Diameter

Tuesday 14:00 — 15:30, Session A (Auditorium)

14:00 Michal Feldman, Ophir Friedler and Aviad Rubinstein — 99% Revenue via Enhanced Competition
Pieter Kleer and Guido Schaefer — Computing good Nash equilibria in combinatorial congestion games
Laure Daviaud, Marcin Jurdzinski and Ranko Lazic — A pseudo-quasi-polynomial algorithm for solving mean-payoff parity games
Yun Kuen Cheung, Richard Cole and Yixin Tao — Dynamics of Distributed Updating in Fisher Markets
Ana-Andreea Stoica, Christopher Riederer and Augustin Chaintreau — Algorithmic Glass Ceiling in Social Networks
14:30 Dušan Knop, Martin Koutecky and Matthias Mnich — A Unifying Framework for Manipulation Problems
Emilio Cruciani, Emanuele Natale, André Nusser and Giacomo Scornavacca — Phase Transition of the 2-Choices Dynamics on Core-Periphery Networks
Yossi Azar and Danny Vainstein — Tight Bounds for Clairvoyant Dynamic Bin Packing
Yossi Azar and Noam Touitou — Improved Online Algorithm for Weighted Flow Time
Marcin Bienkowski, Jaroslaw Byrka and Marcin Mucha — Dynamic Beats Fixed: On Phase-based Algorithms for File Migration
15:00 Nikhil Bansal, Marek Elias and Grigorios Koumoutsos — Weighted k-Server Bounds via Combinatorial Dichotomies
Nikhil Bansal, Martin Bohm, Marek Elias, Grigorios Koumoutsos and Seeun William Umboh — Nested Convex Bodies are Chaseable
Michael P. Kim, Omer Reingold and Guy Rothblum — Fairness Through Computationally-Bounded Awareness
Arya Mazumdar and Barna Saha — Query Complexity of Clustering with Side Information
Casper Freksen, Lior Kamma and Kasper Green Larsen — Tight Bounds for Feature-Hashing Based Dimensionality Reduction

Tuesday 14:00 — 15:30, Session B (Rm 5A-00)

14:00 Radu Curticapean, Nathan Lindzey and Jesper Nederlof — Tight lower bounds for counting Hamiltonian cycles via matrix rank
Bart M.P. Jansen and Astrid Pieterse — Polynomial Kernels for Hitting Forbidden Minors under Structural Parameterizations
Andreas Schmid and Jens M. Schmidt — Computing Tutte Paths
Robert Krauthgamer and Ohad Trabelsi — The Set Cover Conjecture and Subgraph Isomorphism with a tree pattern
Hans L. Bodlaender, Jesper Nederlof and Tom van der Zanden — Tight algorithms and lower bounds for graph embedding problems in planar and H-minor free graphs
14:30 Mikkel Abrahamsen, Anna Adamaszek, Karl Bringmann, Vincent Cohen-Addad, Mehran Mehr, Eva Rotenberg, Alan Roytman and Mikkel Thorup — Fast Fencing
Matthias Bentert, René van Bevern and Rolf Niedermeier — (Wireless) Scheduling, Graph Classes, and c-Colorable Subgraphs
Eric Blais, Clément Canonne, Talya Eden, Amit Levi and Dana Ron — Tolerant Junta Testing and the Connection to Submodular Optimization and Function Isomorphism
Asaf Shapira and Lior Gishboliner — Removal Lemmas with Polynomial Bounds
Federico D'Ambrosio, Gerard Barkema and Hans L. Bodlaender — Optimal data structures for stochastic driven simulations
15:00 Robert Tarjan and Caleb Levy — Zip Trees
Adrian Kosowski and Przemysław Uznański — Ergodic Effects in Token Circulation
Karl Däubel, Frieder Smolny, Yann Disser, Torsten Mütze, Max Klimm and Aaron Bernstein — Distance-Preserving Graph Contractions
Davis Issac, L. Sunil Chandran and Yun Kuen Cheung — Spanning Tree Congestion and Computation of Generalized Győri-Lovász Partition
Lucas Farach-Colton, Martin Farach-Colton, Reut Levi, Moti Medina and Miguel Mosteiro — Closure Operators and Spam Resistance for PageRank