in $\{0,1\}$ and the addition is modulo 2. We require exact recovery for $x^V$ and consider for the underlying graph $G=(V,E)$, with $V=[n]$, both the Erdős-Rényi model $\mathrm{ER}(n,p)$ where the edges are drawn i.i.d. with probability $p$, and deterministic $d$-regular graphs. We assume that the noise vector $Z^E$ has i.i.d. components, equal to 1 with probability $\varepsilon$. We assume[^5] w.l.o.g. that $\varepsilon\in [0,1/2]$, where ${\varepsilon}= 0$ means no noise (and exact recovery amounts to having a connected graph) and ${\varepsilon}= 1/2$ means maximal noise (and exact recovery is impossible no matter how connected the graph is). The prior on $x^V$ is assumed to be uniform. Note that the inverse problem would be much easier if the noise model caused erasures with probability $\varepsilon$, instead of errors. Exact recovery would then be possible if and only if the graph was still connected after the noisy edges had been erased. Since there is a sharp threshold for connectedness at $p=\frac{\log(n)}{n}$, this would happen a.a.s. if $p=\frac{(1+\delta)\log(n)}{n(1-\varepsilon)}$ for some $\delta>0$. Hence $1/(1-{\varepsilon})$ is a sharp threshold in $np/\log(n)$ for the exact recovery problem with erasures and base-graph $\mathrm{ER}(n,p)$.

The goal of this paper is to find the replacement to the erasure threshold $1-{\varepsilon}$ 