ISL Colloquium
The ISL Colloquium convenes in person again (on Thursdays at 4pm PT in Packard 101) as of Fall 2021. For those unable to attend, talks are also streamed via Zoom. To avoid "Zoom-bombing", we ask attendees to input their email address here to receive the Zoom meeting details via email.

← List all talks ...

A Very Sketchy Talk

David Woodruff – Professor, CMU

Fri, 13-Nov-2020 / 1:15pm / Zoom:

Note the unusual day, time and Zoom link!



We give an overview of dimensionality reduction methods, or sketching, for a number of problems in optimization, first surveying work using these methods for classical problems, which gives near optimal algorithms for regression, low rank approximation, and natural variants. We then survey recent work applying sketching to column subset selection, kernel methods, sublinear algorithms for structured matrices, tensors, trace estimation, and so on. The focus in the talk will be on fast algorithms.


David Woodruff has been an associate professor at Carnegie Mellon University in the Computer Science Department since 2017. Before that he was a research scientist at the IBM Almaden Research Center, which he joined in 2007 after completing his Ph.D. at MIT in theoretical computer science. His research interests include data stream algorithms, distributed algorithms, machine learning, numerical linear algebra, optimization, sketching, and sparse recovery. He is the recipient of the 2020 Simons Investigator Award, the 2014 Presburger Award, and Best Paper Awards at STOC 2013, PODS 2010, and PODS, 2020. At IBM he was a member of the Academy of Technology and a Master Inventor.