|
|||||
- SOHEIL BEHNEZHAD, University of Maryland
Locality and the Stochastic Matching Problem [PDF]
-
In the stochastic matching problem, we are given an arbitrary graph G, and the goal is to find a matching of an unknown random subgraph G' of G by querying only a small number of edges in G.
In this talk, we show how with the machinery of distributed local algorithms, one can analyze a (non-distributed and global) Monte Carlo algorithm for the stochastic matching problem and prove that it obtains an almost maximum size matching.
Based on joint works with M. Hajiaghayi and M. Derakhshan (STOC'20, FOCS'20).
- SEBASTIAN BRANDT, ETH Zurich
Round Elimination: A Technique for Proving Distributed Lower Bounds [PDF]
-
Traditionally, proving substantial time complexity lower bounds in the LOCAL model of distributed computing has been a challenging and little-understood task. The last years, however, have seen the emergence of a conceptually simple, yet powerful technique, called Round Elimination, that provides a blueprint for proving such lower bounds and has been responsible for a number of lower bounds for problems central to the LOCAL model, such as Lovász Local Lemma, Maximal Matching, or Maximal Independent Set. In this talk, we will take a close look at the round elimination technique, its inner workings, potential and limitations.
- SERI KHOURY, Simons Institute, UC Berkeley
The congest model: a glimpse into the challenges that arise due to bandwidth limitations. [PDF]
-
Given a synchronized communication network of n nodes, and a function $f$ of its topology, how fast can the nodes compute $f$? Questions of this kind are central in the study of distributed graph algorithms. Typically, two variants are considered: In the first, the bandwidth of a single message is unlimited (the LOCAL model), and in the second, it is limited by $O(\log n)$ bits (the CONGEST model).
In this talk we discuss the challenges that arise due to bandwidth limitations. In particular, we show that even functions that admit $O(1)$-round algorithms in LOCAL, can be very hard in CONGEST.
- HUANG LINGXIAO, Institute for Interdisciplinary Information Sciences
Coreset construction for clustering: offline and distributed settings [PDF]
-
Coreset is a commonly used data reduction technique that is a weighted subset of the data that allow for fast approximate inference for a large dataset by solving the problem on the smaller coreset. In this talk, I will take the clustering problem as an example and introduce a useful framework for coreset construction, called importance sampling. Then I will discuss the connection between coreset and distributed computing, including the composability of coreset, a general “merge-and-reduce” reduction technique, and related applications in distributed settings.
- YANNIC MAUS, Technion, Israel Institute of Technology
Distributed Graph Coloring Made Easy [PDF]
-
The LOCAL model was introduced by Linial [FOCS'87] and studies how far messages need to travel in message passing algorithms to solve some problem in a given communication network. Linial also gave an extremely fast algorithm to color a network (graph) with $O(\Delta^2)$ colors where $\Delta$ is the graph's maximum degree. It became a central research question to efficiently reduce the $O(\Delta^2)$ colors to $\Delta+1$ colors, which is the existential minimum. We survey results and show that, surprisingly, the state of the art algorithm is in close relation to Linial's original algorithm.