exact recovery converges to $1$ as the size of the graph is arbitrarily large. In the context of our particular problem, that claim was also shown in [@Wang_RobustSynchronization]. Later, this analysis was improved by Chen, Huang, and Guibas [@Chen_Huang_Guibas_Graphics] and, when restricted to our setting, it includes guarantees on the rates at which this phase transition happens. However, these rates are, to the best of our knowledge, only optimal up to polylog factors. On the other hand, we are able to show near tight rates. For a given $\epsilon$ that is arbitrarily close to $\frac12$ we give an essentially-tight bound (off by at most a factor of $2$) on the size of the graph and edge density needed for exact recovery (Theorem \[SDP\_ErdosReinyi\]). To the best of our knowledge, our Theorem \[SDPtheoremfordregular\] is the only available result for deterministic graphs.

On the IT side, both converse and direct guarantees were independently obtained by Chen and Goldsmith [@Chen_Goldsmith_ISIT2014]. However, while considering a more general problem, the results they obtain are only optimal up to polylog factors.

Model and results
=================

In this paper, we focus on the linear Boolean model $$\begin{aligned}
Y^E=B_G x^V \oplus Z^E, \label{lin2}\end{aligned}$$ where the vector components are 