\, X  \succeq 0.$$ Note that (\[SDP\_Z2Synch\]) is an SDP and can be solved, up to arbitrary precision, in polynomial time [@LVanderberghe_SBoyd_1996]. Note that a solution of (\[SDP\_Z2Synch\]) need not be rank 1 and thus need not be a solution of (\[noSDP\_Z2Synch\]). However, we will show that under certain conditions recovers the same optimal solution as . In this case, $g_i = (-1)^{x_{i}}$ is the only non-trivial eigenvector of $X$ and $x^V$ can be recovered via the tractable program (\[SDP\_Z2Synch\]).

**Notation:** Recall that $G$ is the underlying graph on $n$ nodes, and let $H$ be the subgraph representing the incorrect edges (corresponding to $Z_{(i,j)}=1$). Let $A_G$, $A_H$, $D_G$, $D_H$, $L_G$, and $L_H$ be, respectively, the adjacency, degree, and Laplacian matrices of the graphs $G$ and $H$.

As in [@ASinger_2011_angsync], we assume w.l.o.g.[^9] that $x^V \equiv 0$ so that $g \equiv 1$. Then, $W = A_G -2A_H$, and (\[SDP\_Z2Synch\]) can be rewritten as: $$\label{SDP_Z2Synch00}
 \max  {\operatorname{Tr}}\left[(A_G -2A_H)X\right] \quad \text{s.t. } X_{ii}=1, \, X  \succeq 0.$$

Our objective is to understand when $X=gg^T=11^T$ is the unique optimal solution to (\[SDP\_Z2Synch00\]). The dual of the SDP is $$\label{SDP_Z2Synch2dual}
 \min  {\operatorname{Tr}}(Q) \quad \text{s.t. } Q\text{ diagonal}, \, Q-\left(A_G -2A_H\right)  \succeq 0.$$ Duality guarantees that 