We develop new methods for analyzing information propagation in branching processes. Our approach is applied to the broadcasting on hypertrees (BOHT) problem, where we obtain the exact reconstruction threshold for a wide range of parameters. As a consequence, we establish the weak recovery threshold for the hypergraph stochastic block model and the condensation threshold for the random NAE-SAT problem in the corresponding parameter regimes, resolving conjectures made by physicists. Our method introduces a rigorous version of population dynamics and improves robust reconstruction analysis. The core of our analysis relies on information-theoretic methods for channel comparison.
Probability and Combinatorics
Tuesday, October 22, 2024 - 3:30pm
Yuzhou Gu
NYU
Other Events on This Day
There are no other events scheduled for this day.