Abstract: Graph coloring problems are among the most extensively studied problems in the area of distributed graph algorithms. The inherent interaction between local and global aspects of the coloring problems makes them representative for a variety of problems in distributed setting. In the distributed graph coloring problem, we are given an undirected graph node of the graph such that no edge is monochromatic. The most fundamental graph coloring problem in distributed computing is $(\Delta+1)$-coloring which can be easily solved by a sequential greedy algorithm, but the interaction between local and global aspects of graph coloring creates some non-trivial challenges in a distributed setting. The problem has been used as a benchmark to study distributed symmetry breaking in graphs, and it is at the very core of the area of distributed graph algorithms. A generalization of $(\Delta+1)$-coloring is the (degree+1)-list coloring (D1LC) problem which is more challenging to solve in the distributed models. In this talk, we discuss the results on coloring problems in Massively Parallel Computation (MPC) and distributed computing with focus on some recent developments on (degree+1)-list coloring (D1LC) problem.

Abstract: In this talk, we consider the vertex-partition model, where the vertices of an input graph are partitioned among $k$ players who communicate via message passing, and the goal is to output the solution to a graph problem. In the extreme case where $k = n$, the model coincides with standard distributed computing models. For $k \ll n$, on the other hand, it can be viewed as a theoretical model for iterative graph processing systems that follow the "think like a vertex" paradigm, which includes, e.g., Pregel and Giraph. We will survey algorithmic results for concrete problems such as maximal matching, as well as discuss the technical difficulties of showing lower bounds that, similarly to the distributed graph sketching model, emanate from the fact that every edge may be known by two players.

Abstract: Sampling edges from a graph in sublinear time is a fundamental problem and a powerful subroutine for designing sublinear-time algorithms. Suppose we have access to the vertices of the graph and know a constant-factor approximation to the number of edges. An algorithm for pointwise $\varepsilon$-approximate edge sampling with complexity $O(n/\sqrt{\varepsilon m})$ has been given by Eden and Rosenbaum [SOSA 2018]. This has been later improved by T\v{e}tek and Thorup [STOC 2022] to $O(n \log(\varepsilon^{-1})/\sqrt{m})$. At the same time, $\Omega(n/\sqrt{m})$ time is necessary. We close the problem by giving an algorithm with complexity $O(n/\sqrt{m})$ for the task of sampling an edge exactly uniformly.