Monday, August 19 2019
15:30 - 17:00

#### Work on the following two problems will be presented 1. Given a data matrix $A\in R^{n\times d}$, containing a set of $n$ points in $R^d$ with $k$ outliers, we study the problem of learning the outliers such that the remaining set of points best fit into some unknown $r$-dimensional subspace. We obtain a randomized approximation algorithm running in time n^{\log n r^2/\epsilon^2} providing (1+\epsilon)OPT guarantee w.h.p. This is joint work with Kirill, Fahad, and Fedor Fomin 2. We study the problem of matrix completion that is given a matrix $A$ (over some field) with missing entries, the goal is to complete the entries of $A$ so as to minimize its rank. We obtain following results a) $p^{O(k.r)} poly(n,m)$ fpt algorithm where $p$ is the size of the field, $k$ is the number of rows with missing entries and $r$ is the desired rank of the output matrix. b) $2^k poly(k+r)$ kernel c) $f(k,r)poly(n,m)$ FPT algorithm on real field where $f$ is some funciton.

Download as iCalendar

Done