ADGA 2022

11th Workshop on Advances in Distributed Graph Algorithms · Augusta · 24 October 2022

ADGA is a one-day workshop that focuses on the theoretical foundations of distributed graph algorithms. The program consists of six invited talks, which are aimed at the general DISC audience.

The talks are designed to cover general aspects of a research topic rather than to present a particular new result. Such aspects include the advances achieved in the topic, the main remaining objectives, the technical obstacles, etc.

ADGA 2022 will be held on Monday, 24 October 2022, and will be co-located with DISC 2022. For information about the registration, please go to the DISC 2022 registration page. The workshop will be chaired by Alkida Balliu.

For information on past and future ADGA workshops, see the web site of the ADGA workshop series.


ADGA programme
8:55 welcome
9:00 talk 1 François Le Gall: Quantum Distributed Computing
10:00 coffee break
10:30 talk 2 Pierre Fraigniaud: Speedup Theorems for All
11:30 talk 3 Michal Dory: Distance Computation in Massive Graphs
12:30 lunch
14:00 talk 4 Orr Fischer: Massively Parallel Computation in a Heterogeneous Regime: One Strong Machine Makes a Big Difference
15:00 talk 5 Yi-Jun Chang: Distributed Graph Algorithms in Minor-Free Networks
16:00 coffee break
16:30 talk 6 Sepehr Assadi: Lower Bounds for Distributed Sketching
17:30 workshop ends

Invited Speakers

[Sepehr Assadi]

Sepehr Assadi

Rutgers University

Sepehr Assadi is an Assistant Professor of Computer Science at Rutgers University. His primary research interests are in theoretical foundations of processing massive datasets and in particular streaming and sublinear time algorithms and lower bounds for massive graph problems. He received a Ph.D. in Computer Science from University of Pennsylvania in 2018 and spent a year as a postdoctoral researcher at Princeton University, before joining Rutgers. His PhD dissertation has won the EATCS Distinguished Dissertation Award, ACM-EATCS Principles of Distributed Computing Dissertation Award, and Rubinoff Dissertation Award from the University of Pennsylvania.

Lower Bounds for Distributed Sketching

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.

[Yi-Jun Chang]

Yi-Jun Chang

National University of Singapore

Yi-Jun Chang is an assistant professor in the Department of Computer Science at the National University of Singapore. Previously, he was a junior fellow in the Institute for Theoretical Studies at ETH Zurich. He received his Ph.D. in Computer Science and Engineering from the University of Michigan in 2019. He is broadly interested in theoretical computer science, focusing on the design and analysis of distributed, parallel, and sublinear graph algorithms. He received the best paper award and the best student paper award at PODC 2019. His doctoral dissertation received the 2020 ACM-EATCS Principles of Distributed Computing Doctoral Dissertation Award.

Distributed Graph Algorithms in Minor-Free Networks

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.

[Michal Dory]

Michal Dory

University of Haifa

Michal Dory has recently joined the Department of Computer Science at the University of Haifa as an assistant professor. Prior to that, she was a post-doctoral researcher at ETH Zurich, in the group of Prof. Mohsen Ghaffari. She received her PhD from the Technion in 2020, under the supervision of Prof. Keren Censor-Hillel. Her research interests are in distributed computing and graph algorithms. Her works received several awards, including the best paper award in PODC 2020, and the best student paper award in PODC 2019.

Distance Computation in Massive Graphs

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.

[Orr Fischer]

Orr Fischer

Weizmann Institute of Science

Orr Fischer is a Postdoctoral fellow at the Weizmann Institute of Science in Prof. Merav Parter’s group. His PhD studies were conducted in Tel-Aviv University under the guidance of Prof. Rotem Oshman, focusing on algorithms, lower bounds, and barriers relating to protocols in networks with bandwidth limitations. Other than distributed computing, Orr’s interests include communication complexity, and most algorithmic settings.

Massively Parallel Computation in a Heterogeneous Regime: One Strong Machine Makes a Big Difference

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.

[Pierre Fraigniaud]

Pierre Fraigniaud

Université Paris Cité and CNRS

Pierre Fraigniaud is “Directeur de Recherche” at CNRS. He is member of “Institut de Recherche en Informatique Fondamentale” (IRIF), affiliated to both Université Paris Cité and CNRS. His main research interest is parallel and distributed computing, and specifically the design and analysis of distributed algorithms and data structures for networks. He is member of the Editorial Boards of Distributed Computing (DC), and Theory of Computing Systems (TOCS). He was Program Committee Chair of FUN in 2022, IPDPS Track Algorithms in 2017, ICALP Track Foundations of networked computation in 2014, ACM PODC in 2011, DISC in 2005, ACM SPAA in 2001, and EuroPar in 1996. In 2012, he received the Silver Medal from CNRS, and, in 2014, the Prize for Innovation in Distributed Computing.

Speedup Theorems for All

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.

[François Le Gall]

François Le Gall

Nagoya University

François Le Gall is a Professor in the Graduate School of Mathematics, Nagoya University. He did his undergraduate studies in France and received his PhD in 2006 from the University of Tokyo. His research interests include algorithms, computational complexity and quantum computation. In the past few years he has been working on the design of quantum distributed algorithms.

Quantum Distributed Computing

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.