Abstract
In the last few years, Michael Cohen has developed faster algorithms for many important problems in optimization such as Laplacian, directed Laplacian, min cost flow, geometric median, matrix scaling, linear/lp regression, clustering,
In the first few minutes of the talk, I will review some of the great achievements in optimization by Michael.
Then, I will present his yet another great achievement, the first input sparsity polynomial time algorithm for lp regression for 1<p<inf. Except for l2 regression, this is the first problem that we can solve in input sparsity time with running time polynomial to log(1/eps).
Joint work with Sébastien Bubeck, Michael Cohen and Yuanzhi Li.