ADGA is a one-day workshop that focuses on the theoretical foundations of distributed graph algorithms. The programme consists of several invited talks, which are aimed at the general DISC audience.
|9:00 am||talk 1||Moti Medina: A (Centralized) Local Guide|
|10:00 am||coffee break|
|10:30 am||talk 2||Andreas Karrenbauer: Continuous Optimization Methods for Network Problems|
|11:30 am||talk 3||Magnus Halldorsson: Graph abstractions in wireless networking|
|12:30 pm||lunch break|
|2:00 pm||talk 4||Mohsen Ghaffari: LOCAL Algorithms: The Chasm Between Deterministic and Randomized|
|3:00 pm||talk 5||Juho Hirvonen: Proving lower bounds in the LOCAL model|
|4:00 pm||coffee break|
|4:30 pm||talk 6||Adrian Kosowski: Distance Labeling: Understanding the Source of Hardness|
|5:30 pm||Workshop ends|
Department of Electrical and Computer Engineering, Ben-Gurion University, Israel
Moti Medina will be joining Ben-Gurion University of the Negev, Department of Electrical & Computer Engineering in the upcoming Fall. Previously, Moti was a post-doc researcher in D1: Algorithms and Complexity at Max-Planck-Institut für Informatik and, a post-doc researcher in the Algorithms and Complexity group at LIAFA (Paris 7). Moti graduated his PhD studies at the School of Electrical Engineering at Tel-Aviv University, in 2014, under the supervision of Prof. Guy Even and Prof. Boaz Patt-Shamir.
A (Centralized) Local Guide
Massive graphs, which contain millions and even billions of nodes, modeling the Internet, the World Wide Web, semantic networks and social networks, are being analyzed and processed constantly. As a result, classical models of computation, in which polynomial-time algorithms are considered efficient, may become inadequate. In the field of sublinear-time algorithms, the goal is to design extremely fast algorithms that probe only a minuscule portion of the input. Likewise, if the size of the output grows linearly in the size of the input, then it becomes desirable to provide access to parts of the output without having to store and compute it entirely. This is where Local Computation Algorithms (or the CentLocal model), as defined by Rubinfeld et al., comes into play.
In this talk I will focus on CentLocal algorithms for computational graph problems. I will start with a comparison of the CentLocal model with other models of computation which are “local” such as: (1) distributed local computation, (2) property testing, and (3) sublinear approximation algorithms. Each of these models has some limitations on the way it accesses the input, and the way it produces the output. I then will elaborate on studied connections of these models to the CentLocal model. I will overview on some of the techniques which are frequently used for designing CentLocal algorithms followed by an overview of the current state-of-the-art algorithms for various graphs problems in terms of the already established tools. At the end of the talk I will present Local Graph Generators. These oracles provide a (sublinear) probe access to a graph drawn from a certain distribution of random graphs. I will outline an implementation of such an oracle that gives access to a graph which is drawn from the Barabási-Albert Preferential Attachment model, and the random recursive tree model.
This talk is based on a recently published survey paper by Reut Levi and myself.
Max-Planck-Institut für Informatik, Saarbrücken, Germany
Andreas Karrenbauer is a Senior Researcher in the Algorithms and Complexity Department of the Max Planck Institute for Informatics in Saarbrücken, Germany. His research interests are in in the area of mathematical optimization. He obtained his PhD from Saarland University, Germany, in 2007. He worked as a Postdoc at EPFL before moving to the University of Konstanz in 2010 to become a Research Fellow and a Research Group Leader. Since 2013, he is the head of the Discrete Optimization Group at the Max Planck Center for Visual Computing and Communication.
Continuous Optimization Methods for Network Problems
Shortest Path, Max Flow, and Min Cut are classical combinatorial optimization problems that have been studied extensively for decades, and many combinatorial algorithms have been developed to solve them. However, they can also be considered as convex optimization problems and, thus, can be attacked by continuous methods as well, such as gradient descent and interior point method. Recently, these techniques were combined with combinatorial structures such as sparsifiers, spanners, low-stretch trees, and congestion approximators to obtain efficient algorithms in centralized and distributed models of computation. We formulate Shortest Path and Max Flow in undirected graphs as norm-minimization problems w.r.t. the 1-norm and the infinity-norm, respectively. We exploit duality and an analytical approximation of the infinity-norm to deal with non-smoothness and obtain near-optimal distributed algorithms.
School of Computer Science, Reykjavik University, Iceland
Magnus M. Halldorsson is a professor in the School of Computer Science of Reykjavik University, where he is the Director of Icelandic Center of Excellence in Theoretical Computer Science (ICE-TCS). He received his Ph.D. in 1991 from Rutgers University and worked at Tokyo Institute of Technology, Japan Advanced Institute of Science and Technology, University of Iceland, and Iceland Genomics. For the last decade, he has focused on algorithms for wireless scheduling with provable performance guarantees. He founded the Workshop on Realistic Models and Algorithms for Wireless Networks (WRAWN) series, that is a leading venue for algorithm theory in wireless networking. He received Best Paper Awards from SIROCCO and ICALP this year.
Graph abstractions in wireless networking
When communication goes wireless, the “network” isn’t necessarily a graph. It could be formulated as a form of a geometric hypergraph, since transmission success depends on the set of other active nodes. Such formulations are necessarily unwieldy, both for the design and analysis of algorithms, whether distributed or centralized. Instead, one could hope for a graph abstraction that captures the interference conflicts conservatively while paying a small price in performance. We outline recent progress along these lines and its implications.
Mohsen Ghaffari is an Assistant Professor in the Computer Science department of ETH Zurich, since Fall of 2016. Before joining ETH, Mohsen received his PhD at MIT, advised by Nancy Lynch.
LOCAL Algorithms: The Chasm Between Deterministic and Randomized
The wide gap between deterministic and randomized algorithms underlies one of the central and well-known questions in Distributed Graph Algorithms. For many of the classic local problems—e.g., MIS or coloring—, while we know very simple O(log n) round randomized algorithms, obtaining a polylog n round deterministic algorithm remains a long-standing open question, since Linial's 1986 paper. This question has gained even more significance recently, due to the findings that show that to obtain faster randomized algorithms, we inevitably need to find faster deterministic algorithms.
In this talk, I will survey some of the recent developments on this topic, in three parts:
- I will start with a complexity-theoretic characterization of this gap, which led to some surprising completeness-type results. One of these completeness results can be interpreted as showing that rounding continuous variables to integer variables, while approximately preserving some linear constraints, is all that remains to be solved deterministically.
- In the second part, I explain how we have been able to attack this rounding question algorithmically in some special cases, leading to (improved) efficient deterministic algorithms for maximal matching and (2Δ−1)-edge coloring, the latter solving a central open problem from the 1990s, as well as a few other problems.
- In the last part, I overview some recent (and unpublished) results, which enable us to solve a much wider range of problems deterministically, including stronger cases of the rounding problem. This part can be viewed as a general and simple-to-state recipe for derandomizing local distributed algorithms.
IRIF and the Université Paris Diderot, Paris, France
Juho Hirvonen defended his thesis in 2016 at the Aalto University, Finland, supervised by Jukka Suomela. He is currently a postdoctoral researcher at IRIF and the Université Paris Diderot, hosted by Pierre Fraigniaud.
Proving lower bounds in the LOCAL model
I will survey the recent advances in lower bound techniques for the LOCAL model. I will focus on two approaches that have proven to be powerful: “algorithmic” simulation lower bounds and the lifting of lower bounds from weaker models.
Simulation techniques have provided both strong and simple distributed computing lower bounds in the recent years. Göös et al. (PODC 2014) used a series of simulation arguments to lift a linear-in-Δ lower bound for maximal fractional matching to the standard LOCAL model. Brandt et al. (STOC 2016) used a simulation to show that a randomized algorithm for the sinkless orientation problem implies a weaker and faster algorithm, proving a lower bound of Ω(log log n) rounds. Chang et al. (FOCS 2016) gave a number of different simulation results, showing for example that algorithms with certain complexities can be automatically sped up and that randomized lower bounds imply even stronger deterministic lower bounds. I will try to illustrate the core intuition of some of these proofs and give a taste of the techniques used.
I will also talk about how some these results are starting to form a complexity theory of distributed graph algorithms, at least for the case of relatively sparse graphs. I want to highlight some of the major open questions, the shortcomings of our current proof techniques, and also some possible ways forward.
INRIA and Université Paris Diderot, Paris, France
Adrian Kosowski is a permanent researcher at Inria Paris. Since 2014, he has been part of the Inria project GANG, affiliated with the “Complex Systems, Networks, and Distributed Computing” team of the Research Institute for Foundations of Computer Science (IRIF, Paris Diderot University). His research interests focus on distributed and local algorithms, discrete dynamical systems, and emergent phenomena in interaction networks. He also holds a part-time teaching position at Ecole Polytechnique.
Distance Labeling: Understanding the Source of Hardness
Distance labeling schemes can be viewed as an abstract framework for formulating algorithms and distributed data structures to answer distance queries on node pairs in a graph. In this talk, we will overview 15 years of progress in the area, with a focus on recent developments for the case when the desired outcome is an exact (rather than approximate) distance computation or an exact shortest path computation. We will try to shed some light on why the complexity of the distance labeling problem still remains wide open for some of the most basic graph classes, such as sparse graphs and planar graphs. More broadly, we will try to provide some insights into the principle sources of hardness of designing distributed graph oracles for the considered type of query.