Yuzhou Gu, Institute for Advanced Study

Abstract

We study the weak recovery problem on the r-uniform hypergraph stochastic block model (r-HSBM) with two balanced communities. In this model, n vertices are randomly divided into two communities, and size-r hyperedges are added randomly depending on whether all vertices in the hyperedge are in the same community. The goal of the weak recovery problem is to recover a non-trivial fraction of the communities given the hypergraph. This model generalizes the stochastic block model and has relationships with constraint satisfaction problems such as NAE-SAT and hypergraph bicoloring.

In the graph (r=2) case, Massoulié '14 and Mossel-Neeman-Sly '15 established that possibility of weak recovery is governed by a simple formula called the Kesten-Stigum (KS) threshold. For general r, Pal-Zhu '21 proved that weak recovery is always possible above the KS threshold. In this talk I will discuss a number of results regarding tightness of the KS threshold. In particular, we show that KS is tight when (a) r is at most four, or (b) r is at most six, and average degree d is large enough, or (c) d is small enough; KS is not tight when r is at least seven, and d is large. The impossibility results are proved using channel comparison tools from information theory. The possibility results are proved using a simple inefficient estimator.

Based on joint works with Aaradhya Pandey and Yury Polyanskiy. 

See: https://sites.google.com/view/rutgersdmseminar