April 12, 2019
12:00 PM - 1:00 PM
Title: Sublinear Algorithms for Graph Coloring
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? 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 on joint work with Sepehr Assadi and Yu Chen.
Bio: Sanjeev Khanna is a Henry Salvatori Professor of Computer and Information Science at the University of Pennsylvania. Sanjeev’s primary research interests are in approximation algorithms and hardness of approximation, combinatorial optimization, and sublinear algorithms.