Abstract
Despite the success of complexity of low-polynomial time for combinatorial problems, little is known about the exact polynomial time complexity of linear algebra problems. I will discuss a few variants of the low rank approximation problem, including Frobenius, robust, weighted, and spectral low rank approximation. I will show how sketching techniques can be used to obtain optimal input sparsity time algorithms for Frobenius and robust versions of low rank approximation. I will also discuss several lower bound techniques used for robust and weighted low rank approximation. The main open question is whether there is an input sparsity time algorithm for spectral low rank approximation. I will describe what is known about this problem.