Sketching Graphs and Matrices

Modern algorithms commonly have to process and store enormous networks, which are represented as graphs or matrices.  Classic methods are often way too slow to be effective on these huge inputs.  Rather than abandoning our textbook algorithms altogether, though, a popular modern way to attack this problem is by creating a “sketch” of the input, which is a smaller version that faithfully preserves its important properties.  The sketch can then be quickly and effectively analyzed instead of the original.

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.