2020 IEEE International Symposium
on Information Theory
21-26 June 2020 • Los Angeles, California, USA
| Paper ID | I.2.3 | ||
| Paper Title | Broadcasting on trees near criticality | ||
| Authors | Yuzhou Gu, Hajir Roozbehani, Yury Polyanskiy, Massachusetts Institute of Technology, United States | ||
| Session | I.2: Broadcast Channel II | ||
| Presentation | Lecture | ||
| Track | Network Information Theory | ||
| Manuscript | Click here to download the manuscript | ||
| Virtual Presentation | Click here to watch in the Virtual Symposium | ||
| Abstract | We revisit the problem of broadcasting on $d$-ary trees: starting from a Bernoulli$(1/2)$ random variable $X_0$ at a root vertex, each vertex forwards its value across binary symmetric channels $\BSC_\delta$ to $d$ descendants. The goal is to reconstruct $X_0$ given the vector $X_{L_h}$ of values of all variables at depth $h$. It is well known that reconstruction (better than a random guess) is possible as $h\to \infty$ if and only if $\delta < \delta_c(d)$. In this paper, we study the behavior of the mutual information and the probability of error when $\delta$ is slightly subcritical. The innovation of our work is application of the recently introduced ``less-noisy'' channel comparison techniques. For example, we are able to derive the positive part of the phase transition (reconstructability when $\delta<\delta_c$) using purely information-theoretic ideas. This is in contrast with previous derivations, which explicitly analyze distribution of the Hamming weight of $X_{L_h}$ (a so-called Kesten-Stigum bound). | ||
Plan Ahead
2021 IEEE International Symposium on Information Theory
11-16 July 2021 | Melbourne, Victoria, Australia
