Henry Salvatori Professor of Computer and Information Science
Department of Computer & Information Science
University of Pennsylvania
Sublinear Algorithms for Graph Coloring
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? In this talk, we will present results that answer this question in the affirmative for several well-studied models of sublinear computation including graph streaming, sublinear time, and massively parallel computation (MPC). We obtain these results by proving a palette sparsification theorem which says that if every vertex independently samples O(log n) colors, then almost certainly a (Delta + 1) coloring can be found using only the sampled colors. We will show that this palette sparsification theorem naturally leads to essentially optimal sublinear algorithms in each of the above-mentioned models of computation.
This is based onjoint work with Sepehr Assadi and Yu Chen.