Special Colloquium
Greg Bodwin
Georgia Tech
Sketching Graphs
Abstract: 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.
Friday February 14, 2020 at 3:00 PM in 636 SEO