Feb 14 2020

Special Colloquium: Sketching Graphs, by Greg Bodwin

February 14, 2020

3:00 PM - 3:50 PM


636 SEO


Chicago, IL

Greg Bodwin (Georgia Tech): Sketching Graphs

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 spectrum. We end with a 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.

Please click here to make changes to, or delete, this seminar announcement.


Will Perkins

Date posted

Feb 18, 2020

Date updated

Feb 18, 2020


Greg Bodwin | (Georgia Tech)