Technical Program

Paper Detail

Paper IDI.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

Visit Website!