  The Burer-Monteiro method is one of the most widely used techniques for
solving large-scale semidefinite programs (SDP). The basic idea is to solve a
nonconvex program in $Y$, where $Y$ is an $n \times p$ matrix such that $X = Y
Y^T$. In this paper, we show that this method can solve SDPs in polynomial time
in a smoothed analysis setting. More precisely, we consider an SDP whose domain
satisfies some compactness and smoothness assumptions, and slightly perturb the
cost matrix and the constraints. We show that if $p \gtrsim \sqrt{2(1+\eta)m}$,
where $m$ is the number of constraints and $\eta>0$ is any fixed constant, then
the Burer-Monteiro method can solve SDPs to any desired accuracy in polynomial
time, in the setting of smooth analysis. Our bound on $p$ approaches the
celebrated Barvinok-Pataki bound in the limit as $\eta$ goes to zero, beneath
which it is known that the nonconvex program can be suboptimal.
  Previous analyses were unable to give polynomial time guarantees for the
Burer-Monteiro method, since they either assumed that the criticality
conditions are satisfied exactly, or ignored the nontrivial problem of
computing an approximately feasible solution. We address the first problem
through a novel connection with tubular neighborhoods of algebraic varieties.
For the feasibility problem we consider a least squares formulation, and
provide the first guarantees that do not rely on the restricted isometry
property.
