  Consider the semigroup of random walk on a complete graph, which we call the
Potts semigroup. Diaconis and Saloff-Coste computed the maximum of the ratio of
the relative entropy and the Dirichlet form obtaining the constant $\alpha_2$
in the $2$-log-Sobolev inequality ($2$-LSI). In this paper, we obtain the best
possible non-linear inequality relating entropy and the Dirichlet form (i.e.,
$p$-NLSI, $p\ge1$). As an example, we show $\alpha_1 = 1+\frac{1+o(1)}{\log
k}$.
  By integrating the $1$-NLSI we obtain the new strong data processing
inequality (SDPI), which in turn allows us to improve results of Mossel and
Peres on reconstruction thresholds for Potts models on trees. A special case is
the problem of reconstructing color of the root of a $k$-colored tree given
knowledge of colors of all the leaves. We show that to have a non-trivial
reconstruction probability the branching number of the tree should be at least
$$\frac{\log k}{\log k - \log(k-1)} = (1-o(1))k\log k.$$ This recovers previous
results (of Sly and Bhatnagar et al.) in (slightly) more generality, but more
importantly avoids the need for any coloring-specialized arguments. Similarly,
we improve the state-of-the-art on the weak recovery threshold for the
stochastic block model with $k$ balanced groups, for all $k\ge 3$. To further
show the power of our method, we prove optimal non-reconstruction results for a
broadcasting on trees model with Gaussian kernels, closing a gap left open by
Eldan et al. These improvements advocate information-theoretic methods as a
useful complement to the conventional techniques originating from the
statistical physics.
