by $\log n$ edges. Moreover, assume the two graphs that are obtained by disconnecting the two components have Cheeger constant $h_G$ and minimum degree $c \log n$, where $c$ is some positive constant for which the sufficient condition of Theorem \[th:CheegerDirPart\] holds. Then, Theorem \[th:CheegerDirPart\] implies that each component can be recovered correctly (up to an inevitable additive offset). Moreover, with high probability less than half of the $\log n$ edges that connect the two components are corrupted by noise. Hence, ML decoding indeed recovers the correct vertex-variables up to a constant additive binary offset. But the Cheeger constant of the graph satisfies $h_g \leq 2 / \left( c n \right)$ and thus converges to zero as $n$ approaches infinity. This leaves the interesting open question of investigating a characteristic of the graph that captures how easy it is to solve (on it) the type of inverse problems considered here.

Computationally efficient recovery - the SDP
============================================

In this section we analyze a tractable method to recover $x^V$ from the noisy measurements $Y^E$, which is based on SDP. Ideally, one would like to find the maximum likelihood estimator $x^\ast = {\operatorname{argmin}}_{x_i \in \{0,1\}} \sum_{(i,j)\in E} 1_{\left\{x_i  \neq y_{(i,j)} \oplus x_j 