Many computational problems induced by practice arise at the intersection of
discrete, numerical, and randomized algorithms. Combining insights from
multiple 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
* The first O(m polylog(n)) time algorithm for approximating undirected
maximum flows, a fundamental problem in combinatorial optimization.
* The first nearly optimal sampling routine that preserves the L1-norms of
matrix-vector products, a common structure in data analysis.
These algorithms rely on connections between iterative methods, flows/cuts,
and sampling drawn through structured matrices. Ideas in them 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 a generalization of matrix concentration bounds