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, 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. |

URI: | http://arks.princeton.edu/ark:/88435/dsp01m039k765c |

Type of Material: | Princeton University Senior Theses |

Language: | en |

Appears in Collections: | Mathematics, 1934-2020 |

Files in This Item:

File | Description | Size | Format | |
---|---|---|---|---|

BOIX-ENRIC-THESIS.pdf | 333.99 kB | Adobe PDF | Request a copy |

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