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. We end with some open problems and future research directions in the area, and a discussion of how the various results and techniques for sketching different graph properties relate to one another.
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.
A reception for attendees will be held in CS 150 at 3:30 p.m.