for the setting where the noise causes errors. Similarly to channel coding where the Shannon capacity of the BSC$(\varepsilon)$ differs from the BEC$(\varepsilon)$ capacity, we obtain for the considered inverse problem the expression $$\begin{aligned}
D(1/2||{\varepsilon}) & = (1-2{\varepsilon})^2/2 + o((1-2{\varepsilon})^2) \nonumber \\ & =\log(2)-H({\varepsilon})+o((1-2{\varepsilon})^2),\end{aligned}$$ where $D(1/2||{\varepsilon})$ is the Kullback-Leibler divergence[^6] between $1/2$ and $\varepsilon$. Hence the Shannon capacity provides the threshold for the low-SNR regime, although the considered inverse problem is a priori not related to the channel coding theorem.

More precisely, this paper establishes an IT necessary condition that holds for every graph (Theorem \[th:convKLDiv\]), an IT sufficient condition for Erdős-Rényi graphs (Theorem \[th:suffCondErdRen\]), and an IT sufficient condition that holds for any graph (Theorem \[IT\_sufficient\_CheegerConstant\]) and depends on the graph’s Cheeger constant, a common measure of the connectivity of a graph (see (\[def:Cheegerconstant44\])) related to its spectral gap by Cheeger’s inequality (see Theorem \[thm:Cheegersineq\]). Moreover, we also give a recovery guarantee that holds for an efficient algorithm based on SDP (Theorems \[SDP\_ErdosReinyi\] and \[SDPtheoremfordregular\]).

In particular, we show that, for ${\varepsilon}\to \frac12$ and $\frac12-{\varepsilon}= \Omega \! \left( n^{-\tau} \right)$ for every $\tau > 0$: The bounds for the necessary condition for a general graph and the IT sufficient 