of the ground truth, we have thus shown:

If $$\label{conditionneededdual}
 L_G - 2L_H\succeq 0 \text{ and } \lambda_2(L_G - 2L_H) > 0,$$ then $gg^T$, where $g_i = (-1)^{x_{i}}$ corresponds to the ground truth, is the unique solution to (\[SDP\_Z2Synch\]).

Erdős-Rényi Model
-----------------

We now assume that the underlying graph is drawn from the Erdős-Rényi model $\mathrm{ER}(n,p)$ and use condition (\[conditionneededdual\]) to give guarantees for exact recovery.

For each pair of vertices $i<j$, let $\Lambda_{ij}$ be an $n\times n$ symmetric matrix with $\Lambda_{ij}(i,i) = 1$, $\Lambda_{ij}(j,j) = 1$, $\Lambda_{ij}(i,j) = \Lambda_{ij}(j,i) = -1$, and $\Lambda_{ij}(k,l) = 0$ for all other pairs $(k,l)$. Observe that $\Lambda_{ij}\succeq 0$, and $
 L_G = \sum_{i<j:(i,j)\in E} \Lambda_{ij}.
$ Let $\alpha_{ij}$ be the random variable that takes the value $0$ if edge $(i,j)$ is not in $G$, the value $1$ if it is in $G$ but not in $H$, and the value $-1$ if it is in $H$. Hence $\alpha_{ij}$ are i.i.d. with distribution $$\alpha_{ij} = \left\{ \begin{array}{cl}  
    0 & \text{ with probability } 1-p \\
     1 & \text{ with probability } p \left(1-\varepsilon\right) \\ 
     -1 & \text{ with probability } p \varepsilon.
       \end{array}   \right.$$

In the new notation, $$L_G - 2L_H = \sum_{i< j} \alpha_{ij}\Lambda_{ij}.$$ 