  We study the weak recovery problem on the $r$-uniform hypergraph stochastic
block model ($r$-HSBM) with two balanced communities. In HSBM a random graph is
constructed by placing hyperedges with higher density if all vertices of a
hyperedge share the same binary label, and weak recovery asks to recover a
non-trivial fraction of the labels. We introduce a multi-terminal version of
strong data processing inequalities (SDPIs), which we call the multi-terminal
SDPI, and use it to prove a variety of impossibility results for weak recovery.
In particular, we prove that weak recovery is impossible below the
Kesten-Stigum (KS) threshold if $r=3,4$, or a strength parameter $\lambda$ is
at least $\frac 15$. Prior work Pal and Zhu (2021) established that weak
recovery in HSBM is always possible above the KS threshold. Consequently, there
is no information-computation gap for these cases, which (partially) resolves a
conjecture of Angelini et al. (2015). To our knowledge this is the first
impossibility result for HSBM weak recovery.
  As usual, we reduce the study of non-recovery of HSBM to the study of
non-reconstruction in a related broadcasting on hypertrees (BOHT) model. While
we show that BOHT's reconstruction threshold coincides with KS for $r=3,4$,
surprisingly, we demonstrate that for $r\ge 7$ reconstruction is possible also
below KS. This shows an interesting phase transition in the parameter $r$, and
suggests that for $r\ge 7$, there might be an information-computation gap for
the HSBM. For $r=5,6$ and large degree we propose an approach for showing
non-reconstruction below KS, suggesting that $r=7$ is the correct threshold for
onset of the new phase.
