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.

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

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

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

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

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.

Appeared in SODA 2017. Search for paper

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

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.

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

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.

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

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

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

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

Appeared in STOC 2017. Search for paper

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

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

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

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.

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

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.

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

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

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

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