Abstract:We establish the exact reconstruction thresholds for a class of broadcasting models on hypertrees over a symmetric binary alphabet. As a consequence, we show that the condensation threshold coincides with the Kesten-Stigum threshold for random NAE-SAT and random hypergraph bicoloring with arity at most four at any temperature, confirming a prediction of Ricci-Tersenghi et al. '19. We also determine the exact weak recovery threshold for the two-community hypergraph stochastic block model in certain parameter regimes.
The proof combines an improved robust non-reconstruction analysis with a computer-assisted rigorous population dynamics algorithm. It relies heavily on information-theoretic tools, in particular the theory of binary memoryless symmetric channels and channel comparison methods.
From: Yuzhou Gu [view email]
[v1]
Fri, 19 Jun 2026 19:10:09 UTC (181 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。