Multifaceted Algorithm Design via Graph Laplacians
| Speaker: | Richard Peng |
|---|---|
| Affiliation: | MIT |
| Room: | Mathematics and Computer Building (MC) 5417 |
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 nearly-linear work, polylog depth parallel 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 that has motivated the development of many algorithmic tools.
- The first nearly optimal subsampling algorithms that preserve the L1-norms of matrix-vector products, a common structure in data analysis.
These algorithms rely on connections between iterative methods, graph cuts, and sparsification drawn through Laplacian matrices of undirected graphs. Components in them that may be of independent interest include: sparsified matrix squaring as a computational primitive, a solution to the chicken-and-egg problem of utilizing and constructing high quality preconditioners, and extensions of matrix concentration bounds to general p-norms.