Faculty Candidate Seminar
Sketching Graphs and Matrices
This event is free and open to the publicAdd to Google Calendar
In this talk we will survey the “sketching method,” including some recent successes, techniques, and barriers in the area. We will focus mainly on the problem of sketching the distances of a graph, but we will also mention some other properties like cuts or edge pseudorandomness. We end with some open problems and future research directions, and a discussion of how the various results and techniques for sketching different graph properties can potentially be unified.
Bio: Greg Bodwin is a researcher in theoretical computer science. Greg got his Ph.D. from MIT in 2018 and is currently a postdoc in the ARC center at Georgia Tech. His research is about the information complexity of properties of mathematical objects like graphs, matrices, or metrics, and how this can inform modern algorithms for analyzing huge versions of these objects.