#### Room 327

#### Credit Seminar

#### Yogesh Dahiya

##### IMSc

*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.

Done