/ \log 2), \label{eq:singer1}
$ previously shown in [@ASinger_2011_angsync Section 5]. If $\varepsilon \in \left( 0,1/2 \right)$ does not depend on $n$, then this condition only implies $d = \Omega \! \left( 1 \right)$ and is thus weaker than $d = \Omega \! \left( \log n \right)$, which follows from Theorem \[th:convKLDiv\]. If $\varepsilon \to 1/2$, then $H \! \left( \varepsilon \right) = \log 2 - (1-2{\varepsilon})^2 / 2 + o \! \left( (1-2 {\varepsilon})^2 \right)$, and we can write the condition in [@ASinger_2011_angsync] as $1 - 2{\varepsilon}= \Omega \bigl( \sqrt {1/d} \bigr)$. If there is a $\tau^\prime < 2/3$ for which $1 - 2{\varepsilon}\geq n^{-\tau^\prime/2}$, then Theorem \[th:convKLDiv\] is tighter: it implies $1 - 2{\varepsilon}= \Omega \bigl( \sqrt {\log \! \left( n \right)/d} \bigr)$. However, if there is no such $\tau^\prime$, then Theorem \[th:convKLDiv\] cannot be applied.[^8]

Sufficient Conditions for Successful Recovery
---------------------------------------------

We next present sufficient conditions for exact recovery. We first focus on graphs from the Erdős-Rényi model. Then, we consider arbitrary graphs and present a condition that is sufficient for every graph and depends only on the graph’s Cheeger constant.\
For a random base-graph $G = (V,E)$ from the Erdős-Rényi model, we require the vertex-variables $x^V$ 