All Dates/Times are Australian Eastern Standard Time (AEST)

Technical Program

Paper Detail

Paper IDD5-S2-T3.1
Paper Title Broadcasting on Trees Near Criticality: Perturbation Theory
Authors Qian Yu, University of Southern California, United States; Yury Polyanskiy, MIT, United States
Session D5-S2-T3: Reconstruction on Graphs
Chaired Session: Friday, 16 July, 22:20 - 22:40
Engagement Session: Friday, 16 July, 22:40 - 23:00
Abstract Consider a setting where a single bit is broadcast down the $d$-ary tree, where each edge acts as a binary symmetric channel with a crossover probability $\delta$. The goal is to reconstruct the root bit given the values of all bits at a large distance $h$ from the root. It is known the reconstruction is impossible iff $(1-2\delta)^2 d \le 1$. In this paper, we show that in the regime where the latter product converges to 1 from the above, the distribution of the log-likelihood ratio (LLR) of the root bit given the far-away boundary (normalized by the square root of deviation of $\delta$ from criticality) converges to an explicit Gaussian distribution. This strengthens a similar result of Jain-Koehler-Liu-Mossel (COLT'2019) and enables us to resolve conjectures stated in Gu-Roozbehani-Polyanskiy (ISIT'2020) for the scaling of the probability of error and mutual information near criticality. Our results also provide a rationale for the ubiquitous $\mathcal{N}(\mu,2\mu)$ approximation of the LLR distribution in the EXIT-chart heuristics.