The complexity of matrix completion.

Nicholas J. A. Harvey, David R. Karger, Sergey Yekhanin

Browse the full SODA paper archive.