recovery at low-SNR. In addition, an efficient recovery algorithm based on semidefinite programming is proposed and shown to succeed in the threshold regime up to twice the optimal rate. For a deterministic graph $G$, defining the degree rate as $\alpha=d/\log(n)$, where $d$ is the minimum degree of the graph, it is shown that the proposed method achieves the rate $\alpha> 4((1+\lambda)/(1-\lambda)^2)/(1-2{\varepsilon})^2+ o(1/(1-2{\varepsilon})^2)$, where $1-\lambda$ is the spectral gap of the graph $G$.\
    A preliminary version of this paper appeared in ISIT 2014 [@conferenceversion]. This version will appear in the IEEE Transactions on Network Science and Engineering.
address:
- 'Emmanuel Abbe is with the Program in Applied and Computational Mathematics (PACM) and the Department of Electrical Engineering, Princeton University, Princeton, NJ 08544, USA. E-mail: [eabbe@princeton.edu]{}.'
- 'Afonso S. Bandeira is with PACM, Princeton University, Princeton, NJ 08544, USA. E-mail: [ajsb@math.princeton.edu]{}.'
- 'Annina Bracher is with the Department of Electrical Engineering, Swiss Federal Institute of Technology, Zurich, ZH 8092, CH. E-mail: [bracher@isi.ee.ethz.ch]{}.'
- 'Amit Singer is with the Department of Mathematics and PACM, Princeton University, Princeton, New Jersey 08544, USA. E-mail: [amits@math.princeton.edu]{}.'
author:
- 'Emmanuel Abbe, Afonso S. Bandeira, Annina Bracher, and Amit Singer'
bibliography:
- 'ExactRecovery.bib'
- 'gen.bib'
title: 'Decoding binary 