Computational Limits for Matrix Completion

A new approximate graph coloring algorithm

Avi Wigderson · 1982

Earlier work this paper cites.

A better performance guarantee for approximate graph coloring

B. Berger and J. Rompel · 1990

Earlier work this paper cites.

Orthogonal representations over finite fields and the chromatic number of graphs

René Peeters · 1996

Earlier work this paper cites.

An o ⁡ ( n 3 / 14 ) o(n^{3/14}) -coloring algorithm for 3-colorable graphs

Blum and Karger · 1997

Earlier work this paper cites.

Approximate graph coloring by semidefinite programming

David Karger, Rajeev Motwani, and Madhu Sudan · 1998

Earlier work this paper cites.

Efficient svm training using low-rank kernel representations

Shai Fine and Katya Scheinberg · 2002

Earlier work this paper cites.

The em algorithm for kernel matrix completion with auxiliary data

Koji Tsuda, Shotaro Akaho, and Kiyoshi Asai · 2003

Earlier work this paper cites.

New approximation guarantee for chromatic number

Sanjeev Arora, Eden Chlamtac, and Moses Charikar · 2006

Cited alongside, same era.

The complexity of matrix completion

Nicholas J. A. Harvey, David R. Karger, and Sergey Yekhanin · 2006

Cited alongside, same era.

Approximation algorithms using hierarchies of semidefinite programming relaxations

Eden Chlamtac · 2007

Cited alongside, same era.

Complexity measures of sign matrices

Nati Linial, Shahar Mendelson, Gideon Schechtman, and Adi Shraibman · 2007

Cited alongside, same era.

Exact matrix completion via convex optimization

Emmanuel J. Candès and Benjamin Recht · 2009

Cited alongside, same era.

The power of convex relaxation: near-optimal matrix completion

Emmanuel J. Candès and Terence Tao · 2010

Cited alongside, same era.

A simpler approach to matrix completion

Benjamin Recht · 2011

Later among the works it cites.

Rank minimization over finite fields: Fundamental limits and coding-theoretic interpretations

V.Y.F. Tan, L. Balzano, and S.C. Draper · 2012

Later among the works it cites.

Complexity theoretic lower bounds for sparse principal component detection

Quentin Berthet and Philippe Rigollet · 2013

Later among the works it cites.

Complexity of the positive semidefinite matrix completion problem with a rank constraint

Marianna E.-Nagy, Monique Laurent, and Antonios Varvitsiotis · 2013

Later among the works it cites.

Algorithms and hardness for robust subspace recovery

Moritz Hardt and Ankur Moitra · 2013

Later among the works it cites.

Coloring 3-colorable graphs with o ⁡ ( n 1 / 5 ) o(n^{1/5}) colors

Ken ichi Kawarabayashi and Mikkel Thorup · 2014