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.