Programme
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 complexityIn 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(log^{2} n) ReplacementsAppeared 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(n^{1/3})) Samples + Optimal Mean-based Algorithms for Trace ReconstructionAppeared 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 StructuresAppeared 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 HittersAppeared 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 problemsMany 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. |
17:00 — 17:30 |
Sergio Cabello — Subquadratic Algorithms for the Diameter and the Sum of Pairwise Distances in Planar GraphsAppeared in SODA 2017. Search for paper |
17:30 — 18:00 |
Aviad Rubinstein — Distributed PCP Theorems for Hardness of Approximation in PAppeared 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 — LOCAL distributed algorithms |
10:00 — 10:30 |
Seth Pettie — A Time Hierarchy Theorem for the LOCAL ModelAppeared 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 AlgorithmsIn 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. |
12:00 — 12:30 |
Moses Charikar — A Hitting Time Analysis of Stochastic Gradient Langevin DynamicsAppeared 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 TSPAppeared 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 TimeAppeared 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 MoreAppeared 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-subgraphAppeared 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 DisjointnessAppeared in FOCS 2017; coauthored with Mark Braverman. Search for paper |
9:30 — 10:00 |
Krzysztof Nowicki — MST in O(1) Round of Congested CliqueAppeared in SODA 2018; coauthored with Tomasz Jurdzinski. Search for paper |
10:00 — 10:30 |
Magnús Halldorsson — Universal Framework for Wireless Scheduling ProblemsAppeared 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 lemmaA 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 coverAppeared 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 dimensionsTraditionally, 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) QuestionsAppeared 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 revisitedAppeared 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 GraphsAppeared 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-SumAppeared 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 Õ(log^{2} n) Amortized Time | |
Sayan Bhattacharya, Deeparnab Chakrabarty, Monika Henzinger and Danupon Nanongkai — Dynamic Algorithms for Graph Coloring | |
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 | |
14:30 | Gopal Pandurangan, Peter Robinson and Michele Scquizzato — A Time- and Message-Optimal Distributed Algorithm for Minimum Spanning Trees |
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 | |
15:00 | Laurent Feuilloley and Pierre Fraigniaud — Error-Sensitive Proof-Labeling Schemes |
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 Huiberts — 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 |