Seminar Details
Weak Recovery Threshold for the Hypergraph Stochastic Block Model
- Start Date: March 4, 2024
- Event Start Time: 2:00 PM
- Event End Time: 3:00 PM
- Seminar Series: Rutgers Discrete Mathematics Seminar
- Presenter(s): Yuzhou Gu - Institute for Advanced Study
- Event Location: Conference Room 705 | Rutgers University | Hill Center | 110 Frelinghuysen Rd
- Event Additional Info: <p>See: <a href="https://sites.google.com/view/rutgersdmseminar">https://sites.google.com/view/rutgersdmseminar</a></p>
- Presentation Type: Stand Alone Presentation
- 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.