Seminar Details
Distributed Degree+1-Coloring and Applications
- Start Date: May 4, 2022
- Event Start Time: 11:00 AM
- Event End Time: 12:00 PM
- Seminar Series: Theoretical Computer Science Seminar
- Presenter(s): Magnús Halldórsson - Reykjavik University
- Event Location: Online Event
- Event Additional Info: <p>Special Note: The Theory of Computing Seminar is being held online. Contact the organizers for the link to the seminar. </p> <p>See: <a href="https://theory.cs.rutgers.edu/theory_seminar" target="_blank">https://theory.cs.rutgers.edu/theory_seminar</a> </p>
- Presentation Type: Stand Alone Presentation
- Abstract:
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.