Exact reconstruction thresholds on hypertrees over a symmetric binary alphabet (opens in new tab)

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