An Information-Percolation Bound for \(\mathbb{Z}/2\mathbb{Z}\) Synchronization

Abstract

We derive information-theoretic bounds for reconstruction in \(\mathbb{Z}/2\mathbb{Z}\) synchronization. Specifically, given a graph \(G\) whose vertices are labelled with i.i.d. Rademacher-\(1/2\) variables \(X_v\), and whose edges \((u,v)\) are labelled with outputs \(Y_{uv}\) of channels on \(X_u \cdot X_v\), we upper-bound the information that the edge labels give about the vertex labels.

Our bounds relate the information given by \((X_u,Y)\) about \(X_v\) to the connection probability between \(u\) and \(v\) in a suitable bond percolation on \(G\). The proof is a simple interpolation argument.

As applications of our bound, we re-derive known thresholds for impossibility of reconstruction in Broadcasting on Trees [EKPS00], for impossibility of recovery in the Spiked Gaussian Wigner Model [DAM15], and for impossibility of clustering in the Censored Block Model [LMX15]. Our bound also improves on the known threshold [AMM+17] for the impossibility of Grid Synchronization in the case of binary vertex labels.