The talk discusses several classical graph-problems such as computing all pairs shortest paths, and the related problem of computing the diameter in a distributed setting (CONGEST model). For the above mentioned problems, the talk will cover algorithms running in time O(n) in the unweighted case, as well as lower bounds derived from lower bounds on two-party communication complexity of set disjointness showing that this is essentially optimal. After extending these results to approximation algorithms and corresponding lower bounds, the talk will provide insights into lower bounds for distributed verification problems. That is, we study problems such as verifying that a subgraph H of a graph G is a minimum spanning tree. In the talk we will see that verifying a spanning tree can take much more time than actually computing a spanning tree of G. As an application of these results we derive strong unconditional time lower bounds on the hardness of distributed approximation for many classical optimization problems including minimum spanning tree, shortest paths, and minimum cut. Many of these results are the first non-trivial lower bounds for both exact and approximate distributed computation and they resolve previous open questions. Our result implies that there can be no distributed approximation algorithm for minimum spanning tree that is significantly faster than the current exact algorithm, for any approximation factor.

Parallel algorithms study ways of speeding up sequential algorithms through concurrently computing on multiple processors. Theoretical parallel algorithms often focus on performing a small number of operations, but assume more generous models of communication.

Recent progresses led to parallel algorithms for many graph optimization problems that have proven to be difficult to parallelize. In this talk I will survey these new algorithmic frameworks and discuss some of their core routines: low diameter decompositions, random sampling, and iterative methods.

In this talk we will discuss the communication complexity of problems in distributed graphs, where we have k machines, each holding a subgraph and they want to jointly compute some function defined on the union of the k subgraphs. The communication is point-to-point, and the goal is to minimize the total communication between the k machines. This model captures all point-to-point distributed computational models with the clique topology in terms of communication complexity, including BSP and MapReduce.

In this talk I will introduce a few techniques developed in the last few years for proving multiparty point-to-point communication lower bounds, and then discuss how to use them for proving lower bounds for graph problems such as connectivity and maximum matching.

I will give an overview of a part of my research journey centered around compact routing. Progress in compact routing had a significant impact on several other research areas. In particular, compact routing has influenced problems in metric embeddings, real world route planning systems, dynamic graph algorithms, distributed systems and more! I will highlight how many of these problems are interrelated and how progress in one field sometime leads to improvements in others.

Peer-to-Peer (P2P) networks — typically overlays on top of the Internet — pose some unique challenges to algorithm designers. The difficulty comes primarily from constant churn owing to the short life span of most nodes in the network. In order to maintain a well-connected overlay network despite churn at this level, the overlay must be dynamically maintained. This makes the overlay network graph an evolving graph that exhibits both edge dynamism and node churn. In this talk, we will discuss the somewhat surprising line of work in which we show how to design fast algorithms that are robust against heavy churn.

We will begin with a discussion on how to create an overlay network that has good expansion despite adversarial churn. Subsequently, assuming such an overlay network with good expansion, we will present a few basic techniques like fast information dissemination, random walks, and support estimation. Finally, we show how to use these techniques to design algorithms to solve fundamental problems like agreement, leader election, storing and retrieving data items.

In the distributed message passing model a communication network is represented by a graph whose vertices host processors that communicate over the edges. Computation proceeds in rounds of local computations and message exchange between neighbors. Our goal is solving graph-theoretic tasks (vertex-coloring, maximal matching, maximal independent set, etc.), where the network graph is the input. The input is provided in a distributed manner, i.e., initially each vertex knows only its neighbors. Eventually, the vertices output their parts in the solution, and the union of these answers constitutes a proper solution for the entire graph. The running time is the number of rounds required for all vertices to output their answers.

Although some networks remain the same throughout the entire execution, other networks are very dynamic and may change significantly. This is the case in wireless ad-hoc networks, social networks, mobile networks and many other networks. In these networks new vertices may join and connect to existing ones, old vertices may crash, and connections between vertices may appear and disappear as a result of movement of vertices, channel failures, etc. Consequently, distributed algorithms must handle not only static networks, but also the ones that change rapidly. In the latter scenario, even when a correct solution has been computed, the network may change, and a correction to the solution may be required. In this case, the number of rounds required for correcting the solution after a topology change is the dynamic running time.

While distributed symmetry breaking has been studied for decades, researchers were able to overcome some complexity barriers only recently. This progress has been achieved thanks to the discovery of novel directions for coloring, maximal independent set, and related symmetry breaking problems. I will survey some classical results in this area and proceed with recent advances that allow for significant improvements in both the static and dynamic settings. I will illustrate how the dynamic setting borrows ideas from the static one, and how it pays back.