« Distributed Degree+1-Coloring and Applications
Distributed Degree+1-Coloring and Applications
May 04, 2022, 11:00 AM - 12:00 PM
Location:
Online Event
Magnús Halldórsson, Reykjavik University
We give a simpler approach to color graphs fast in a distributed manner. In particular, we obtain the first non-trivial randomized algorithm for deg+1-list coloring, a fundamental self-reducible problem variant that appears frequently as a subproblem. Another implication is that we can Delta+1-color graphs of maximum degree Delta > log^3 n in ultrafast log-star time.
One corollary is a palette sparsification result for deg+1-list coloring. When placed in the groundbreaking framework of Assadi, Chen, and Khanna SODA’19, as extended by Alon and Assadi'21, it yields algorithms for three modern models of computing: streaming algorithms, sublinear-time algorithms, and the Massively Parallel Computation model.
This is joint work with Fabian Kuhn (Freiburg), Alex Nolin (RU), and Tigran Tonoyan (ex-RU), to appear in STOC 2022.
Special Note: The Theory of Computing Seminar is being held online. Contact the organizers for the link to the seminar.