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 2024 will be held on Monday, 28 October 2024, and will be co-located with DISC 2024. For information about the registration, please go to the DISC 2024 registration page. The workshop will be chaired by Yannic Maus.
For information on past and future ADGA workshops, see the web site of the ADGA workshop series.
Schedule
ADGA program | ||
---|---|---|
9:30 | talk 1 | Fabian Reiter: Locality via Alternation? |
10:30 | coffee break | |
11:00 | talk 2 | Francesco D'Amore: Causal Limits of Distributed Computation: Bounding Quantum Advantage |
12:00 | talk 3 | Jan Grebik: Measurable combinatorics |
13:00 | lunch | |
14:30 | talk 4 | Michael Kapralov: Sublinear Time Clustering Oracles |
15:30 | talk 5 | Shreyas Pai: On the Message Complexity of Distributed Algorithms |
16:30 | coffee break | |
17:00 | talk 6 | Ran Gelles: Distributed Computing with Signals |
18:00 | workshop ends |
Invited Speakers
Bocconi University
Francesco d'Amore is a postdoctoral researcher at Bocconi University, where he works in the research group previously led by Luca Trevisan. Francesco obtained his Ph.D. in Computer Science from Inria Sophia Antipolis & Université Côte d'Azur in 2022, under the supervision of Emanuele Natale. He later worked as a postdoctoral researcher at Aalto University, Finland, in the distributed computing research group led by Jukka Suomela. Francesco's research focuses on the intersection of distributed computing theory and probability.
Causal Limits of Distributed Computation: Bounding Quantum Advantage
Theoretical quantum advantage is well-established in centralized computing, where computation is performed on a single computer. However, its potential in distributed computing is less understood. In this talk, we consider the LOCAL model of computation (Linial 1987), a model of synchronous distributed computation where the complexity measure is the number of communication rounds needed to solve a problem, with no constraints on communication bandwidth or local computation capabilities. The classical LOCAL model is well-studied, especially regarding Locally Checkable Labeling (LCL) problems (Naor and Stockmeyer 1993), which include problems like graph coloring, finding maximal independent sets, etc. However, determining whether quantum computers and quantum communication can speed up computation in this setting remains an open question. Currently, no tools specific to quantum-LOCAL exist to address this question. Nonetheless, arguments based on independence and causality have been useful in “sandwiching” quantum-LOCAL between classical LOCAL and super-quantum models. This talk will discuss recent findings in this area, highlighting settings where quantum advantage is impossible and where current arguments fail to rule out quantum advantage.
Presentation slides: PDF
Bar-Ilan University in Israel
Ran Gelles is an associate professor at Bar-Ilan University in Israel. He received his B.Sc. (Summa Cum Laude) and M.Sc. from the Technion–Israel Institute of Technology, in 2003 and 2009, respectively. He received his PhD in 2014 from the University of California, Los Angeles (UCLA). His research includes topics in fault tolerance of distributed systems and the incorporation of coding theory techniques in various distributed settings.
Distributed Computing with Signals
This talk is about distributed computation with signals—when devices communicate by sending contentless “pulses” instead of content-based messages. In asynchronous environments, the arrival time of such pulses is arbitrary, and devices can infer information only from the origin of each pulse and their order of arrival. I will review recent Content-Oblivious Algorithms—algorithms for solving various tasks based on point-to-point signaling without the ability to convey information in the content of the transmitted messages.
Presentation slides: PDF
University of Vienna
Gramoz Goranci is an assistant professor at University of Vienna, Austria. Previously, he was a visiting scientist at UC Berkeley and an advanced fellow at ETH Zurich. He completed his postdoc at University of Toronto, held a permanent lectureship at University of Glasgow, and received his PhD from University of Vienna under Monika Henzinger. Gramoz is broadly interested in algorithm design, and its connections to optimization, graph theory and machine learning. His recent work has focused on designing fast dynamic algorithms for graph-based optimization problems.
Dynamic and Distributed Spectral Vertex Sparsifiers
Graph sparsification is a technique that approximates a given graph by another graph, called a sparsifier, which has fewer vertices and/or edges. The goal of a sparsifier is to provably preserve specific graph properties of interest, such as connectivity, shortest paths, and flow/cut structure, among others.
In this talk, I will focus on spectral vertex sparsifiers, which reduce the number of vertices while preserving the graph spectrum. I will explain how to efficiently compute these sparsifiers in dynamically changing graphs and in the distributed CONGEST model. I will also discuss the implications of these results for exact computations of maximum and minimum-cost flows in both the sequential and distributed setting.
UCLA and Masaryk University
Jan Grebik is currently a Marie Skłodowska-Curie postdoctoral fellow at UCLA and Masaryk University. Before that he was a research fellow at the University of Warwick. He completed his PhD at Charles University.
Measurable combinatorics
I will provide a gentle introduction to measurable combinatorics, a field that lies at the intersection of areas that study discrete structures (finite combinatorics, random graphs, distributed computing), analytic objects (descriptive set theory, measured group theory, analysis) and interactions between them (graph limits, stochastic processes). After presenting a couple of fundamental and motivating results, such as the constructible solutions to Tarski's circle-squaring problem, I will focus on the recently discovered connections between the theory of distributed computing and descriptive set theory, which are formalized through the study of complexity classes of locally checkable labeling (LCL) problems.
Presentation slides: PDF
EPFL
Michael Kapralov is an Associate Professor in the School of Computer Sciences at EPFL. He completed his PhD at Stanford, then spent two years as a postdoc at MIT, and a year at IBM as a Goldstine Postdoctoral Fellow. Michael is broadly interested in theoretical computer science, with an emphasis on theoretical foundations of big data analysis. Most of his algorithmic work is in sublinear algorithms, where specific directions include streaming, sketching, sparse recovery and Fourier sampling.
Sublinear Time Clustering Oracles
Given access to a large graph, can we quickly test whether it can be partitioned into a few good clusters? And if so, quickly tell, given a vertex, which cluster it belongs to?
This problem for $k = 2$ clusters is the expansion testing problem, introduced in the classical work of Goldreich and Ron and studied extensively over the following two decades. The main idea of these works is to associate with every vertex the distribution of a short random walk started at it, and then use distance-based Euclidean clustering on the resulting point set—with a careful implementation this leads to an algorithm with runtime $\approx n^{1/2}$ for $k = 2$.
It turns out, however, that ‘distance-based’ clustering methods fundamentally do not extend to any number of clusters higher than 2 without a major loss in efficiency. I will talk about our recent line of work that uses angles as opposed to distances in the corresponding Euclidean space one can optimally test cluster structure for all $k \ge 2$. A key component of our approach is the concept of a spectral clustering oracle, which is a small space data structure that allows dot product access to the spectral embedding of the input graph. This results in close to information theoretically optimal algorithms for testing and querying the cluster structure of the graph.
Indian Institute of Technology Madras
Shreyas Pai is an Assistant Professor in the Department of Computer Science and Engineering at Indian Institute of Technology Madras in Chennai. He received his PhD in Computer Science at The University of Iowa under the supervision of Prof. Sriram V. Pemmaraju in May 2021. Afterwards he was a post-doctoral fellow at Aalto University hosted by Prof. Jara Uitto till March 2024 (supported by HIIT starting August 2023). His research interests are primarily in Theory of Distributed and Parallel Computing, more specifically in Distributed Graph Algorithms and Algorithms for Large Data. He is also more generally interested in topics in Theoretical Computer Science like Communication Complexity and Combinatorial Optimization.
On the Message Complexity of Distributed Algorithms
In this talk we will look at the communication cost (or message complexity) of fundamental problems in the distributed CONGEST model. Message complexity defined as the total number of messages sent by all nodes over the course of the algorithm. We will address the following question in this talk: can we solve problems using sublinear, i.e., $o(m)$ communication, and if so under what conditions? I will give an overview of the known results on message complexity of problems ranging from broadcast and spanning trees, to symmetry-breaking and optimization problems.
Presentation slides: PDF
Gustave Eiffel University
Fabian Reiter has been an associate professor (maître de conférences) at Gustave Eiffel University since 2019. His research interests lie at the intersection of distributed algorithms and formal logic. Previously, he worked as a postdoctoral researcher with Javier Esparza at the Technical University of Munich and with Patricia Bouyer-Decitre and Benedikt Bollig at Paris-Saclay University. He obtained his PhD in 2017 under the supervision of Olivier Carton at Paris Cité University.
Locality via Alternation?
Traditionally, in distributed graph algorithms, the locality of a problem is measured by the number of communication rounds required to solve the problem in the LOCAL model. However, Feuilloley [DMTCS 2021] suggested that for decision problems, the local certification framework could provide a different way of measuring locality: let an external prover assign a certificate to each node, and measure how large the certificates must be for the nodes to locally verify a given graph property (the smaller the certificates, the more local the property).
In this talk, we will explore a third potential measure of locality: quantifier alternation, the key concept underlying the polynomial hierarchy. The proposed thesis is that the locality of a graph property can be measured by the number of alternations in a game between two players who argue whether the network has the property, alternately assigning proofs and counterproofs to the nodes (the fewer alternations needed, the more local the property).
Presentation slides: PDF