  Several probabilistic models from high-dimensional statistics and machine
learning reveal an intriguing --and yet poorly understood-- dichotomy. Either
simple local algorithms succeed in estimating the object of interest, or even
sophisticated semi-definite programming (SDP) relaxations fail.
  In order to explore this phenomenon, we study a classical SDP relaxation of
the minimum graph bisection problem, when applied to Erd\H{o}s-Renyi random
graphs with bounded average degree $d>1$, and obtain several types of results.
First, we use a dual witness construction (using the so-called non-backtracking
matrix of the graph) to upper bound the SDP value. Second, we prove that a
simple local algorithm approximately solves the SDP to within a factor
$2d^2/(2d^2+d-1)$ of the upper bound. In particular, the local algorithm is at
most $8/9$ suboptimal, and $1+O(1/d)$ suboptimal for large degree.
  We then analyze a more sophisticated local algorithm, which aggregates
information according to the harmonic measure on the limiting Galton-Watson
(GW) tree. The resulting lower bound is expressed in terms of the conductance
of the GW tree and matches surprisingly well the empirically determined SDP
values on large-scale Erd\H{o}s-Renyi graphs.
  We finally consider the planted partition model. In this case, purely local
algorithms are known to fail, but they do succeed if a small amount of side
information is available. Our results imply quantitative bounds on the
threshold for partial recovery using SDP in this model.
