Penn Arts & Sciences Logo

Applied Math and Comp Sci Colloquium

Friday, May 3, 2019 - 2:00pm

David Woodruff

Carnegie Mellon University


University of Pennsylvania


In this tutorial, I'll give an overview of near optimal algorithms for regression, low rank approximation, and a variety of other problems. The results are based on the sketch and solve paradigm, which is a tool for quickly compressing a problem to a smaller version of itself, for which one can then run a slow algorithm on the smaller problem. These lead to the fastest known algorithms for fundamental machine learning and numerical linear algebra problems, which run in time proportional to the number of non-zero entries of the input.