SIGACT News 44 (1), March 2013.

Notes: the published version of the article has a few errors.

• Moitra’s SODA paper improves the running time from $O((nm)^{2^r r^2})$ to $O((nm)^{r^2})$, which is considerably stronger than what was reported in the article.
• The correct lower bound for computing a nonnegative factorization (assuming ETH) is $O((nm)^{o(r)})$.

This link (PDF) has the corrected article. Thanks to Ankur Moitra for pointing out the errors.

Tags: Column