### Friday, April 26, 2019 - 11:00am to 12:00pm

### Location:

ASA Conference Room 6115 Gates Hillman Centers### Speaker:

SANJEEV KHANNA, Henry Salvatori Professor of Computer and Information Science https://www.cis.upenn.edu/~sanjeev### 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 on* *joint work with Sepehr Assadi and Yu Chen.*

**Faculty Host:** Anupam Gupta* *