English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Consider the semigroup of random walk on a complete graph, which we call thePotts semigroup. Diaconis and Saloff-Coste computed the maximum of the ratio ofthe 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 bestpossible 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)}{\logk}$.  By integrating the $1$-NLSI we obtain the new strong data processinginequality (SDPI), which in turn allows us to improve results of Mossel andPeres on reconstruction thresholds for Potts models on trees. A special case isthe problem of reconstructing color of the root of a $k$-colored tree givenknowledge of colors of all the leaves. We show that to have a non-trivialreconstruction 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 previousresults (of Sly and Bhatnagar et al.) in (slightly) more generality, but moreimportantly avoids the need for any coloring-specialized arguments. Similarly,we improve the state-of-the-art on the weak recovery threshold for thestochastic block model with $k$ balanced groups, for all $k\ge 3$. To furthershow the power of our method, we prove optimal non-reconstruction results for abroadcasting on trees model with Gaussian kernels, closing a gap left open byEldan et al. These improvements advocate information-theoretic methods as auseful complement to the conventional techniques originating from thestatistical physics.

Non-linear Log-Sobolev inequalities for the Potts semigroup and applications to reconstruction problems