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||Thomas Sauerwald: Random Walks on Dynamic Graphs|
|10:00 am||coffee break|
|10:30 am||talk 2||Sebastian Brandt: Automatic Round Elimination: A New Approach for Proving Complexity Bounds in the LOCAL Model|
|11:30 am||talk 3||Endre Csóka: Random local algorithms from the graph limits perspective|
|12:30 pm||lunch break|
|2:00 pm||talk 4||Silvio Lattanzi: Large scale algorithms, clustering, and the MPC model|
|3:00 pm||talk 5||Thatchaphol Saranurak: Expander decomposition: applications to dynamic and distributed algorithms|
|4:00 pm||coffee break|
|4:30 pm||talk 6||Rotem Oshman: Distributed Property Testing — Progress and Challenges|
|5:30 pm||Workshop ends|
University of Cambridge
Thomas Sauerwald is a Senior Lecturer in the Department of Computer Science and Technology at the University of Cambridge. He obtained his PhD in Computer Science from the University of Paderborn in 2008. After that, he has held positions at the International Computer Science Institute at Berkeley, Simon Fraser University and Max Planck Institute for Informatics. His main research areas are Markov chains as well as randomized and distributed algorithms.
Random Walks on Dynamic Graphs
We establish and generalise several bounds for various random walk quantities including the mixing time and the maximum hitting time. Unlike previous analyses, our derivations are based on rather intuitive notions of local expansion properties which allows us to capture the progress the random walk makes through t-step probabilities. We apply our framework to dynamically changing graphs, where the set of vertices is fixed while the set of edges changes in each round.
For random walks on dynamic connected graphs for which the stationary distribution does not change over time, we show that their behaviour is in a certain sense similar to static graphs. For example, we show that the mixing and hitting times of any sequence of d-regular connected graphs is O(n²), generalising a well-known result for static graphs. Finally, we investigate properties of random walks on dynamic graphs that are not always connected: we relate their convergence to stationarity to the spectral properties of an average of transition matrices and provide some examples that demonstrate strong discrepancies between static and dynamic graphs.
Sebastian Brandt is a postdoc in the Discrete and Distributed Algorithms Group at ETH Zurich, led by Mohsen Ghaffari. He received his PhD from ETH in the beginning of 2018, supervised by Roger Wattenhofer. His research focuses on the study of distributed algorithms, in particular the limitations imposed on them by locality. This year, he will be a recipient of the FOCS Best Paper Award for a work on lower bounds in the LOCAL model.
Automatic Round Elimination: A New Approach for Proving Complexity Bounds in the LOCAL Model
In recent years, the LOCAL model has seen the emergence of a new technique, called "round elimination", that lies at the core of new lower bounds for important problems such as the Lovász Local Lemma, Maximal Matching, or Maximal Independent Set. Despite its conceptual simplicity, it has become one of the main tools in proving round complexity lower bounds for locally checkable problems.
The fundamental insight behind this technique is that, roughly speaking, for each locally checkable problem P, there is another problem P1 that can be solved exactly one round faster. By applying this insight iteratively, obtaining problems P1, P2, … with decreasing complexities, the complexity of P can be bounded by checking which of the Pi is the first problem in the sequence that can be solved in 0 rounds. As we will see, the above sequence of problems can be obtained in a fully automated way, opening new and exciting possibilities for obtaining improved complexity bounds for locally checkable problems. In this talk, we will take an in-depth look at the round elimination technique, its inner workings, potential and limitations.
Alfréd Rényi Institute of Mathematics, Budapest
Endre Csóka is a researcher at Alfréd Rényi Institute of Mathematics, Budapest. His research focuses on graph theory, graph limits and graph algorithms. He earned his PhD at Eötvös University of Budapest in 2013 on local algorithms in large graphs, under the supervision of László Lovász. Then he held a postdoc position at the University of Warwick until 2015. He received the Erdős prize in 2018.
Random local algorithms from the graph limits perspective
We are trying to answer questions such as whether random graphs have the least structure among all locally equivalent graphs. More precisely, we focus on locally defined optimization problems on bounded-degree graphs such as finding a large matching or independent set. In random graphs, our best algorithms for these problems can be approximated by constant-time randomized distributed algorithms called local algorithms. We give an overview about positive and negative results about what can be constructed by them, including some very recent algorithms and entropic bounds. All these questions have strong connections to sparse graph limit theory and statistical physics.
Google Research Zurich
Silvio is a Research Scientist at Google Zurich since April 2017. Before he was part of the NY Algorithm group at Google New York (2011–2017). He received my PhD from Sapienza University of Rome under the supervision of Alessandro Panconesi. His research interests are in the areas of algorithms, machine learning and information retrieval.
Large scale algorithms, clustering, and the MPC model
As a fundamental tool in modeling and analyzing real world data, large-scale algorithms are a central part of any tool set for big data analysis. Processing datasets with hundreds of billions of entries is only possible via developing distributed algorithms under distributed frameworks such as MapReduce, Pregel, Gigraph, and alike. For these distributed algorithms to work well in practice, we need to take into account several metrics such as the number of rounds of computation and the communication complexity of each round. In this talk, we discuss the design and implementation of algorithms based on traditional MapReduce architecture. In this regard, we focus on the MPC model and we consider different clustering problems.
Toyota Technological Institute at Chicago
Thatchaphol Saranurak is a research assistant professor at Toyota Technological Institute at Chicago. His main research interest is efficient graph algorithms, in particular for dynamic and distributed models. Thatchaphol completed his PhD at KTH Royal Institute of Technology in 2018 where he was supervised by Danupon Nanongkai.
Expander decomposition: applications to dynamic and distributed algorithms
Expander decomposition has been a central tool in designing graph algorithms in many fields (including fast centralized algorithms, approximation algorithms and property testing) for decades. Recently, we found that it also gives many impressive applications in dynamic graph algorithms and distributed graph algorithms. In this talk, I will survey these recent results based on expander decomposition, explain the key components for using this technique, and give some toy examples on how to apply these components.
Computer Science Department, Tel Aviv University
I obtained my PhD from MIT under the supervision of Prof. Nancy Lynch, and went on to be a post-doctoral fellow at the University of Toronto and, later on, Princeton University. I am currently a Senior Lecturer in Computer Science at Tel Aviv University. My research interests include communication complexity, distributed computing, and the intersection between distributed computing and general theory of computer science.
Distributed Property Testing — Progress and Challenges
In this talk we will survey some of the recent work on distributed property testing in the networks with bounded bandwidth (the CONGEST model). Property testing is a relaxation of the standard notion of a decision problem, where instead of deciding if the input satisfies some property or not, we are only interested in distinguishing the case where the input has the property from the case where it is far from having the property, in the sense that many bits in the representation of the input would need to be changed to make it satisfy the property. In the case of graph problems, this means adding or removing many edges to the graph. Classical problems studied in the sequential setting include testing subgraph-freeness, bipartiteness, planarity, and many other problems. Several of these have now been studied in the CONGEST model, and I will talk about some of the results, some open problems, and why we currently have very few lower bounds.