Please use this identifier to cite or link to this item: http://arks.princeton.edu/ark:/88435/dsp01m039k765c
 Title: An Information-Percolation Bound for $$\mathbb{Z}/2\mathbb{Z}$$ Synchronization Authors: Boix, Enric Advisors: Sly, AllanAbbe, Emmanuel Department: Mathematics Certificate Program: Applications of Computing Program Class Year: 2018 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. URI: http://arks.princeton.edu/ark:/88435/dsp01m039k765c Type of Material: Princeton University Senior Theses Language: en Appears in Collections: Mathematics, 1934-2020