*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
Essie M. Reynolds
Summary Sentence: SCS Faculty Recruit Seminar - Multifaceted Algorithm Design via Graph Laplacians
Full Summary: No summary paragraph submitted.
Richard PengRichard Peng is an Instructor in Applied Mathematics at MIT. His main research interestes are in the design of methods that provably solve large problems quickly. Richard received his Ph.D. from Carnegie Mellon University in 2013. He was a Microsoft Research Ph.D. Fellow and his thesis won the CMU SCS Distinguished Dissertation Award.
Abstract:
Many computational problems induced by practice arise at the intersection of combinatorics, optimization and statistics. Combining insights from these areas often leads to better algorithms for such problems, as well as improvements to these areas themselves. In this talk, I will discuss some recent progress via this approach:
* A fast solver for linear systems involving graph Laplacians, a core primitive in spectral algorithms and a well-studied routine in scientific computing.
* The first O(m polylog(n)) time algorithm for approximating undirected maximum flows, a fundamental problem in combinatorial optimization.
* The first nearly optimal subsampling algorithms that preserve the L_1-norms of matrix-vector products, a common structure in data analysis.
These algorithms rely on connections between iterative methods, flows, and sampling drawn through the Laplacian matrices of undirected graphs. Components that may be of independent interest include an algorithmic framework based on sparsified matrix squaring, the chicken-and-egg problem of building/utilizing high quality approximations, and extensions of matrix concentration bounds to general p-norms.
