  Denote by $A$ the adjacency matrix of an Erdos-Renyi graph with bounded
average degree. We consider the problem of maximizing $\langle
A-E\{A\},X\rangle$ over the set of positive semidefinite matrices $X$ with
diagonal entries $X_{ii}=1$. We prove that for large (bounded) average degree
$d$, the value of this semidefinite program (SDP) is --with high probability--
$2n\sqrt{d} + n\, o(\sqrt{d})+o(n)$. For a random regular graph of degree $d$,
we prove that the SDP value is $2n\sqrt{d-1}+o(n)$, matching a spectral upper
bound. Informally, Erdos-Renyi graphs appear to behave similarly to random
regular graphs for semidefinite programming.
  We next consider the sparse, two-groups, symmetric community detection
problem (also known as planted partition). We establish that SDP achieves the
information-theoretically optimal detection threshold for large (bounded)
degree. Namely, under this model, the vertex set is partitioned into subsets of
size $n/2$, with edge probability $a/n$ (within group) and $b/n$ (across). We
prove that SDP detects the partition with high probability provided
$(a-b)^2/(4d)> 1+o_{d}(1)$, with $d= (a+b)/2$. By comparison, the information
theoretic threshold for detecting the hidden partition is $(a-b)^2/(4d)> 1$:
SDP is nearly optimal for large bounded average degree.
  Our proof is based on tools from different research areas: $(i)$ A new
`higher-rank' Grothendieck inequality for symmetric matrices; $(ii)$ An
interpolation method inspired from statistical physics; $(iii)$ An analysis of
the eigenvectors of deformed Gaussian random matrices.
