Dartmouth Events

Abstract:  As traditional gold standards of computational efficiency, namely, linear-time and linear-space, no longer seem sufficient for processing massive data sets, a rich new area of sublinear algorithms has emerged. Sublinear algorithms require computational resources that are substantially smaller than the size of the input on which they operate. The past few decades have seen remarkable successes where surprisingly efficient sublinear algorithms have been discovered for many fundamental problems.

In this talk, we will examine a classical graph coloring problem through the lens of sublinear algorithms. 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 present new 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 University of Pennsylvania. He received a Ph.D. in Computer Science from Stanford University in 1996. His doctoral work at Stanford received the 1996 Arthur Samuel prize for the best PhD dissertation in the Computer Science Department. He joined University of Pennsylvania in 1999 after spending three years as a researcher at Bell Laboratories.

Sanjeev’s primary research interests are in approximation algorithms and hardness of approximation, combinatorial optimization, and sublinear algorithms. He is an ACM Fellow, Guggenheim Fellow, and a Sloan Fellow. He is also a recipient of S. Reid Warren, Jr. and Lindback awards for distinguished teaching at University of Pennsylvania.