\right\}}$. By defining the $\{\pm1\}$-valued variables $g_i = (-1)^{x_i}$ and the coefficients $\rho_{ij}=(-1)^{y_{(i,j)}}$, the ML problem is reformulated as $$\label{angsynch:withgs}
\min_{g_i\in\{\pm1\}} \sum_{(i,j)\in E} (g_i - \rho_{ij}g_j)^2.$$ This problem is known to be NP-hard in general (in fact, it is easy to see that it can encode `Max-Cut`). In what follows, we will describe and analyze a tractable algorithm, which was first proposed in [@ASinger_2011_angsync] to approximate the solution of (\[angsynch:withgs\]). We will state conditions under which the algorithm is able to recover the vertex-variables $x^V$. The idea is to consider a natural semidefinite relaxation. Other properties of this SDP have been studied in [@NAlon_ANaor_2006; @Bandeira_LittleGrothendieckOd].

Let $W$ be the $n\times n$ matrix with $W(i,j) = \rho_{ij}$ if $(i,j)\in E$ and $W(i,j) = 0$ otherwise. Problem (\[angsynch:withgs\]) has the same solutions as $
\max_{g_i\in\{\pm1\}} {\operatorname{Tr}}\left[W gg^T\right],
$ which in turn is equivalent to $$\begin{aligned}
\max \  &{\operatorname{Tr}}\left[W X\right] \label{noSDP_Z2Synch}\\
\text{s.t.}\  & X\in{\mathbb{R}}^{n\times n},\ X_{ii} = 1\ \forall i,\   X\succeq 0,\  {\operatorname{Rank}}(X) =1.\notag
$$ (Given the optimal rank 1 solution $X$ of (\[noSDP\_Z2Synch\]), $g_i = (-1)^{x_{i}}$ is the only non-trivial eigenvector of $X$.) As the rank constraint is non-convex, we consider the following convex relaxation $$\label{SDP_Z2Synch}
 \max  {\operatorname{Tr}}\left[WX\right] \quad \text{s.t. } X_{ii}=1, 