Skip navigation
Please use this identifier to cite or link to this item:
Title: An Information-Percolation Bound for \(\mathbb{Z}/2\mathbb{Z}\) Synchronization
Authors: Boix, Enric
Advisors: Sly, Allan
Abbe, 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.
Type of Material: Princeton University Senior Theses
Language: en
Appears in Collections:Mathematics, 1934-2020

Files in This Item:
File Description SizeFormat 
BOIX-ENRIC-THESIS.pdf333.99 kBAdobe PDF    Request a copy

Items in Dataspace are protected by copyright, with all rights reserved, unless otherwise indicated.