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(log2 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(n1/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 —On the Role of Randomization in Local Distributed AlgorithmsMany 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. |
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.