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.
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.
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.
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.
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.
TBA
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).