Graph Problems in the Streaming Model

Graph Problems in the Streaming Model (via Zoom)

Abstract: In today's era of large data, most classical algorithms are incapable of efficiently processing massive amounts of information. Researchers in the past few decades have turned to data streaming algorithms as a way to handle these intractably large datasets. In this talk I will introduce the data stream model and some of its commonly studied variations, with a focus on graph streams and some early results in the field. I will then turn to the results of Assadi, Chen, and Khanna on the existence of sublinear algorithms for the $\Delta$+1-coloring problem. Many of these algorithms depend crucially on some kind of randomization; it is natural to ask whether this use of randomness is necessary. The talk will conclude with a recent breakthrough showing that there are no deterministic single-pass semi-streaming algorithms which output a proper coloring using a sub-exponential (in $\Delta$) number of colors. 
This talk is adapted from an in-class presentation during the Fall 22 iteration of CS 6815. 
 

Bio: Andrew is a 2nd-year PhD student in the Mathematics Department at Cornell, advised by Prof. Ed Swartz. His interests are in combinatorics and discrete geometry, particularly polymatroids and their connections with optimization.