MPI-INF Logo
Campus Event Calendar

Event Entry

What and Who

Parameterized Complexity of Matrix Factorization Problems

David P. Woodruff
IBM Almaden Research Center
Talk

David P. Woodruff is a prominent researcher at IBM Almaden. He graduated his Ph.D. at MIT in 2007 under the supervision of Piotr Indyk. He is the recipient of numerous awards, including the “Presburger Award from EATCS”, the “IBM Pat Goldberg Award”, and the “IBM Master Inventor Award” (with more than 20 U.S. Patents). Also, he is recognized for “Outstanding IBM Research Division Accomplishments” and he is a member of the “IBM Academy of Technology”. He has a strong record of publications in prestigious conferences such as STOC, FOCS, SODA, ICALP, PODS and NIPS. Most recently, he wrote an excellent book “Sketching as a Tool for Numerical Linear Algebra” summarizing a rapidly emerging subfield of TCS which has many applications in machine learning.
AG 1, AG 2, AG 3, AG 4, AG 5, RG1, SWS, MMCI  
AG Audience
English

Date, Time and Location

Tuesday, 25 April 2017
13:00
45 Minutes
E1 4
024
Saarbrücken

Abstract

This will be an overview talk on several NP-hard variants of low rank approximation, including non-negative low rank approximation, weighted low rank approximation, and ell_1-low rank approximation. These problems have important applications in machine learning and numerical linear algebra. I will discuss various ways of coping with hardness for these problems, such as via approximation, parameterized complexity, and through bicriteria solutions.

Parts of this talk are based on my work with Ilya Razenshteyn, and Zhao Song (STOC '16) and with Zhao Song and Peilin Zhong (STOC '17).

Contact

Pavel Kolev
--email hidden
passcode not visible
logged in users only

Pavel Kolev, 04/21/2017 21:30 -- Created document.