  Matrix Completion is the problem of recovering an unknown real-valued
low-rank matrix from a subsample of its entries. Important recent results show
that the problem can be solved efficiently under the assumption that the
unknown matrix is incoherent and the subsample is drawn uniformly at random.
Are these assumptions necessary?
  It is well known that Matrix Completion in its full generality is NP-hard.
However, little is known if make additional assumptions such as incoherence and
permit the algorithm to output a matrix of slightly higher rank. In this paper
we prove that Matrix Completion remains computationally intractable even if the
unknown matrix has rank $4$ but we are allowed to output any constant rank
matrix, and even if additionally we assume that the unknown matrix is
incoherent and are shown $90%$ of the entries. This result relies on the
conjectured hardness of the $4$-Coloring problem. We also consider the positive
semidefinite Matrix Completion problem. Here we show a similar hardness result
under the standard assumption that $\mathrm{P}\ne \mathrm{NP}.$
  Our results greatly narrow the gap between existing feasibility results and
computational lower bounds. In particular, we believe that our results give the
first complexity-theoretic justification for why distributional assumptions are
needed beyond the incoherence assumption in order to obtain positive results.
On the technical side, we contribute several new ideas on how to encode hard
combinatorial problems in low-rank optimization problems. We hope that these
techniques will be helpful in further understanding the computational limits of
Matrix Completion and related problems.
