The University of Arizona
Please note that this event has ended!

Matrix Decompositions and Sparse Graph Regularity


Matrix Decompositions and Sparse Graph Regularity
Series: TRIPODS Seminar
Location: ENR2 S210
Presenter: Greg Bodwin, Georgia Tech. Postdoc researcher in theoretical computer science and combinatorics.

A common goal in computer science, math, and statistics is
to approximate a "complicated" matrix with a "simple" one.  Examples
include low-rank approximation (by the singular value decomposition),
CUR decomposition, cut decomposition, spectral sparsifiers, and many
more.  In this talk, we will survey some of these approximation
methods and set up a framework, which we call the "projection value
decomposition," that captures and explains all of them at the same
time.  Our main application is to some sparse variants of the
Szemeredi regularity lemma, a famous result in graph theory that
promises good statistical approximations of dense graphs.  We unify
and strengthen some recent efforts to extend the lemma to sparse input
graphs with sufficiently pseudorandom properties.

(Pizza, coffee & tea will be provided at 11:20am)