Richard Peng, Georgia Institute of Technology

Abstract

Computing and maintaining large graphs are increasingly important problems in data mining, machine learning, and security. This talk will use progress on two well-studied problems in static and dynamic graph algorithms, net-work flows and dynamic matchings, to discuss a methodology for designing faster algorithm for large graphs motivated by long-standing open problems in data structures.

I will start by describing how studies of network flows led to a focus on residual networks, which in turn motivated faster algorithms as well as more general notions of preconditioning. I will then discuss a similar phenomenon in dynamic graphs, where the current best algorithms for maintaining large matchings utilize kernels built from dual vertex covers.

Video