ADGA 2020

9th Workshop on Advances in Distributed Graph Algorithms · 16 October 2020

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

ADGA 2020 will be held as a virtual workshop on Friday, 16 October 2020, and will be co-located with DISC 2020. The workshop will be chaired by Jara Uitto.

For information on past and future ADGA workshops, see the web site of the ADGA workshop series. For information about the registration, please go to the DISC 2020 website.

Schedule

All times in Berlin time = Central European Summer Time = CEST = UTC+02:00.

ADGA programme
15:00 talk 1 Krzysztof Onak: The Current Landscape of Massively Parallel Algorithms for Graphs · video
15:30 talk 2 Slobodan Mitrović: Recent LCA Techniques through the Lens of Matchings · video
16:00 coffee break
16:20 talk 3 Faith Ellen: Constant-Length Labelling Schemes for Deterministic Radio Broadcast · video
16:50 talk 4 Yannic Maus: Distributed vertex coloring: classic meets modern · video
17:20 coffee break
17:40 talk 5 Dennis Olivetti: Distributed Edge Coloring in Time Quasi-Polylogarithmic in Δ · video
18:10 talk 6 Michael Dinitz: New Graph Spanners and the Greedy Algorithm · video
18:40 Workshop ends

Videos

Invited Speakers

[Michael Dinitz]

Michael Dinitz

Johns Hopkins University

Michael Dinitz is an assistant professor in the Department of Computer Science at Johns Hopkins University. He received his PhD from Carnegie Mellon University in 2010 under Anupam Gupta, and was a postdoctoral fellow at the Weizmann Institute of Science with Robert Krauthgamer and David Peleg. He works broadly in algorithms, with a focus on approximation algorithms, graph algorithms, distributed computing, and theory of networking.

New Graph Spanners and the Greedy Algorithm

Graph spanners (subgraphs which approximately preserve distances) originated in the distributed computing community and have had a huge impact in distributed algorithms and in algorithms more broadly. In this talk we will discuss recent progress on two relatively new variants of graph spanners: $\ell_p$-norm and fault-tolerant spanners. For $\ell_p$-norm spanners this includes tight existential bounds and good approximation algorithms (at least for some parameter settings), and for fault-tolerant spanners this includes tight existential bounds with surprisingly efficient algorithms.

Both of these variants are particularly well-motivated in distributed settings. Yet for both of them the recent progress in the centralized setting is based on some variant of the greedy algorithm, which is not easily implementable in distributed settings. We hope that this talk will help spur research on distributed algorithms for these important objects.

[Faith Ellen]

Faith Ellen

University of Toronto

Faith Ellen received her Ph.D. from the University of California, Berkeley, in 1982, became a faculty member at the University of Washington in 1983, and moved to the University of Toronto in 1986, where she is a Professor of Computer Science. She was the program committee chair for DISC 2002, OPODIS 2018, and PODC 2019, served as the chair of the PODC steering committee from 2006 to 2009, and was vice-president of SIGACT from 1997 to 2001. Her research interests include the theory of distributed computing, data structures, and complexity and she is a co-author of the book “Impossibility Results for Distributed Computing”. Faith became a Fellow of the Association for Computing Machinery in 2014.

Constant-Length Labelling Schemes for Deterministic Radio Broadcast

Broadcast is a fundamental network communication primitive, in which a source node has a message that has to be received by all other nodes. In synchronous radio networks, this problem is non-trivial, since if two or more neighbours of a node transmit at the same time, it hears nothing. In fact, if nodes do not store any information, broadcast is impossible deterministically, even in a four-cycle. If the nodes have distinct identifiers from a small name space, then a round-robin strategy suffices, but it takes a long time.

This talk will show that every radio network can be labelled using a small constant number of bits so that broadcast can be accomplished by a fixed deterministic algorithm that does not know the network topology nor any bound on its size. Specifically, there is a labelling scheme that stores 2 (carefully chosen) bits per nodes that allows broadcast to be performed in $O(n)$ rounds, where $n$ is the size of the network. There is a variant of this algorithm using 4 bits per node that completes broadcast in $O(\sqrt{Dn})$ rounds, where $D$ is the source eccentricity of the network. This number of rounds is shown to be optimal for a class of algorithms that includes both.

Then, using some ideas from some old algorithms, which assume nodes have distinct identifiers and a bound on the network size, a deterministic algorithm is constructed that uses 3 bits per node and completes in $O(D \log^2 n)$ rounds. A randomized construction of a labelling scheme with 3 bits per node for a broadcast algorithm that completes in $O(D \log n + \log^2 n)$ rounds is also presented.

This is joint work with Seth Gilbert and Barun Gorain, Avery Miller, and Andrzej Pelc.

[Yannic Maus]

Yannic Maus

Technion

Yannic Maus is a postdoc at the Technion in the group of Keren Censor-Hillel. His research focused on distributed algorithms, in particular on the limits of randomization and the power of locality. He received his PhD from University of Freiburg, supervised by Fabian Kuhn and, this year, he will be awarded the ACM principles of distributed computing dissertation award.

Distributed vertex coloring: classic meets modern

The last years have seen several new distributed graph coloring algorithms in the LOCAL and the CONGEST model. In this talk we will survey modern techniques and relate (some of) them to classic ones. In particular, we see how Linial’s seminal $O(\Delta^2)$-coloring algorithm for graphs with maximum degree $\Delta$ extends to list coloring and how this implies one of the current state of the art distributed graph coloring algorithms.

[Slobodan Mitrović]

Slobodan Mitrović

MIT

Slobodan Mitrović is a postdoc at MIT, in a group led by Ronitt Rubinfeld. His main research interests are in the area of algorithms in memory-constrained settings, in particular parallel, distributed and streaming. He completed his PhD at EPFL in 2018 under the supervision of Aleksander Mądry.

Recent LCA Techniques through the Lens of Matchings

Local computation algorithms (LCA) formalize concepts that arise in various algorithmic fields. The main task of LCA is to solve a problem on a part of an instance by accessing only "a small" part of it, e.g., deciding whether a given edge is in a maximal matching without looking at the entire graph. In this talk, in the context of matchings, we will discuss two recent LCA techniques. These techniques start with a generic transformation of a LOCAL algorithm to an LCA, and then provide a way to reduce the amount of an input needed to be inspected by the generic approach. One of these techniques has implications for MIS, set cover and coloring as well.

[Dennis Olivetti]

Dennis Olivetti

University of Freiburg

Dennis Olivetti is a postdoc in the Algorithms and Complexity group of Prof. Fabian Kuhn at University of Freiburg, Germany. In 2018 and 2019 he was a postdoc in the Distributed Algorithms group of Prof. Jukka Suomela at Aalto University, Finland. He received his PhD from GSSI, Italy, in December 2017, supervised by Prof. Pierre Fraigniaud. His main research interests are on distributed graph algorithms, and in particular in understanding what can be computed locally.

Distributed Edge Coloring in Time Quasi-Polylogarithmic in $\Delta$

The problem of coloring the edges of an $n$-node graph of maximum degree $\Delta$ with $2\Delta-1$ colors is one of the key symmetry breaking problems in the area of distributed graph algorithms. While there has been a lot of progress towards the understanding of this problem, the dependency of the running time on $\Delta$ has been a long-standing open question. Very recently, Kuhn [SODA ’20] showed that the problem can be solved in time $2^{O(\sqrt{\log \Delta})}+O(\log^* n)$.

In this talk, we discuss the edge coloring problem in the distributed LOCAL model. We show that the (degree+1)-list edge coloring problem, and thus also the $(2\Delta-1)$-edge coloring problem, can be solved deterministically in time $2^{O(\log^2 \log \Delta)} + O(\log^* n)$.

[Krzysztof Onak]

Krzysztof Onak

IBM T.J. Watson Research Center

Krzysztof Onak is a research scientist in the Mathematics of AI group at the IBM T.J. Watson Research Center. His main research interests concern big data computation with limited resources, including algorithms for modern parallel and distributed systems, sublinear-time algorithms, and streaming. Krzysztof received his Master’s degree from the University of Warsaw and his PhD from the Massachusetts Institute of Technology. Before joining IBM, he was a Simons Postdoctoral Fellow at Carnegie Mellon University.

The Current Landscape of Massively Parallel Algorithms for Graphs

One of the most interesting settings for massively parallel algorithms on graphs is when the local space of each machine is sublinear in the number of vertices. This allows for distributing computation, even for sparse graphs, across a large number of machines that do not have to be very powerful. In recent years, we have seen several developments in this area, including both algorithms and conditional lower bounds. In many cases these results leverage connections to other areas such as distributed algorithms and property testing. I will survey some of them and talk in more detail about generating random walks and estimating PageRank, for which we were able to obtain nearly-exponential improvements in round complexity over direct implementations of known algorithms. Finally, I will share some of my favorite open questions in the area.