Max-Planck-Institut für Informatik
max planck institut
informatik
mpii logo Minerva of the Max Planck Society
 

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Parameterized Complexity of Matrix Factorization Problems
Speaker:David P. Woodruff
coming from:IBM Almaden Research Center
Speakers Bio: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.
Event Type:Talk
Visibility:D1, D2, D3, D4, D5, RG1, SWS, MMCI
We use this to send out email in the morning.
Level:AG Audience
Language:English
Date, Time and Location
Date:Tuesday, 25 April 2017
Time:13:00
Duration:45 Minutes
Location:Saarbrücken
Building:E1 4
Room:024
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
Name(s):Pavel Kolev
EMail:pkolev@mpi-inf.mpg.de
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Note:
Attachments, File(s):

Created:
Pavel Kolev, 04/21/2017 09:30 PM
Last modified:
Uwe Brahm/MPII/DE, 04/25/2017 07:01 AM
  • Pavel Kolev, 04/21/2017 09:30 PM -- Created document.