  The most widely used technique for solving large-scale semidefinite programs
(SDPs) in practice is the non-convex Burer-Monteiro method, which explicitly
maintains a low-rank SDP solution for memory efficiency. There has been much
recent interest in obtaining a better theoretical understanding of the
Burer-Monteiro method. When the maximum allowed rank $p$ of the SDP solution is
above the Barvinok-Pataki bound (where a globally optimal solution of rank at
most $p$ is guaranteed to exist), a recent line of work established convergence
to a global optimum for generic or smoothed instances of the problem. However,
it was open whether there even exists an instance in this regime where the
Burer-Monteiro method fails. We prove that the Burer-Monteiro method can fail
for the Max-Cut SDP on $n$ vertices when the rank is above the Barvinok-Pataki
bound ($p \ge \sqrt{2n}$). We provide a family of instances that have spurious
local minima even when the rank $p = n/2$. Combined with existing guarantees,
this settles the question of the existence of spurious local minima for the
Max-Cut formulation in all ranges of the rank and justifies the use of beyond
worst-case paradigms like smoothed analysis to obtain guarantees for the
Burer-Monteiro method.
