Consider the following distributed graph sketching model: There are $n$ players corresponding to vertices of an undirected graph, and each player sees the edges incident on its vertex – this way, each edge is known by both its endpoints and is thus shared by two players. The players communicate in simultaneous rounds by posting their messages on a shared blackboard visible to all players, with the goal of computing a solution to some combinatorial problem on $G$, say, finding a maximal independent set.

This talk will begin with a quick introduction to the surprising power of algorithms in this model, and an overview of the connections of this model to several other well-studied computational model. I will then discuss the challenges in proving lower bounds in this model and survey some recent advances on this front especially for multi-round lower bounds.

In this talk, we consider the algorithm and complexity of distributed graph problems in minor-free networks in the LOCAL and CONGEST models. We will discuss recent results, open questions, and future work directions on this topic.

Computing distances in a graph is one of the most fundamental problems in graph algorithms. But how can we solve it when the input graph is too large and cannot be stored in one computer? In this talk, I will discuss a recent line of work that led to extremely fast distributed algorithms for approximating shortest paths, improving exponentially over the state-of-the-art.

Massively-parallel graph algorithms have received extensive attention over the past decade, with research focusing on three memory regimes: the superlinear regime, the near-linear regime, and the sublinear regime. The sublinear regime is the most desirable in practice, but conditional hardness results point towards its limitations. In particular, the “2-vs-1 cycle” problem, where we are asked to distinguish between a graph that is a single large cycle and graphs that are comprised of two cycles, is conjectured to require $\Omega(\log n)$ rounds. Based on this conjecture and a connection to local distributed algorithms, several conditional hardness results have been shown for sublinear MPC.

In this talk we discuss a heterogeneous setting created by adding a single near-linear space machine to the sublinear MPC regime, and show that this small alteration suffices to circumvent most of the conditional hardness results of the sublinear regime. The starting point of this work is the simple observation that the “2-vs-1 cycle” problem becomes trivial if we have even a single machine with near-linear memory. This motivates us to ask whether the problems whose conditional hardness rests on the hardness of the “2-vs-1 cycle” problem — connectivity, minimum-weight spanning tree, maximal matching, and others — also become easy given a single of large machine.

We will review the known results in this model, discuss which types of techniques work well in this model, and share some of the many open problems in the field.

This talk will provide a brief introduction to the use of algebraic topology for the formulation and analysis of distributed computing. By way of illustration, the presentation will revisit the recent notion of speedup theorem originally developed in the context of local computing in networks, and will reformulate it in the abstract framework of algebraic topology. In particular, it will be shown that speedup theorems can be stated for a large class of different models, even those including asynchrony and failures.

Joint work with Paul Bastide, Ami Paz, and Sergio Rajsbaum.

The subject of this talk will be quantum distributed computing, i.e., distributed computing where the processors of the network can exchange quantum messages. After describing the basics of quantum computing, I will give a survey of recent results, focusing on quantum distributed graph algorithms. I will also describe interesting and important open questions in quantum distributed computing.