Sublinear Algorithms for (Delta+1) Vertex Coloring
, Princeton University
Date: Tuesday, May 21, 2019
Time: 4:00 PM to 5:00 PM
Host: Prof. Ronitt Rubinfeld
Contact: Joanne Talbot Hanley, 617-253-6054, email@example.com
Speaker URL: None
TALK: TOC Seminar: Sepehr Assadi "Sublinear Algorithms for (Delta+1) Vertex Coloring", Tuesday, May 21 at 4pm!
Abstract: In this talk, we will examine a classical graph coloring problem through the lens of sublinear algorithms—these are algorithms that use computational resources that are substantially smaller than the size of the input on which they operate. It is well-known that any graph with maximum degree Delta admits a proper vertex coloring with (Delta + 1) colors that can be found via a simple sequential greedy algorithm in linear time and space. But can one find such a coloring via a sublinear algorithm? We will present results that answer this question in the affirmative for several well-studied models of sublinear computation, most notably graph streaming and sublinear time algorithms. We obtain these results by proving a palette sparsification theorem which says that if every vertex independently samples O(log n) colors from the available Delta+1 colors, then almost certainly a (Delta + 1) coloring can be found using only the sampled colors. We then show that this palette sparsification theorem naturally leads to essentially optimal sublinear algorithms in each of the above-mentioned models of computation.
Based on joint work with Yu Chen and Sanjeev Khanna.
Created by Joanne Talbot Hanley at Wednesday, May 15, 2019 at 11:26 AM.