recovery is typically required in coding theory to ensure reliable communication, while both exact and partial recovery are of interest in community detection problems. This paper focuses on exact recovery for the linear model with Boolean variables, and on random Erdős-Rényi and deterministic base-graphs $G$. For this setup, we identify the information theoretic (IT) phase transition for exact recovery in terms of the edge density of the graph and the noise level and devise an efficient algorithm based on semidefinite programming (SDP), which approaches the threshold up to a factor of $2$ in the Erdős-Rényi case. This SDP based method was first proposed in [@ASinger_2011_angsync], and it shares many aspects with the SDP methods in several other problems [@So_MIMO; @Huang_Guibas_Graphics].

Related work {#abouttheorem51inHuangGuibas}
============

While writing this paper we became aware of various exciting related work that was being independently developed:

A similar exact recovery sufficient condition, as (\[conditionneededdual\]) for the SDP, was independently obtained by Huang and Guibas [@Huang_Guibas_Graphics] in the context of consistent shape map estimation (see Theorem 5.1. in [@Huang_Guibas_Graphics]). Their analysis goes on to show, essentially, that as long as the probability of a wrong edge is a constant strictly smaller than $\frac12$, the probability of 