Sharp Phase Transitions in Estimation with Low-Degree Polynomials

Zoom Link

In the stochastic block model (a canonical model for finding hidden communities in random networks), it has long been conjectured that the so-called Kesten-Stigum (KS) threshold marks the boundary between the "easy" (polynomial-time solvable) and "hard" (computationally intractable) regimes. We substantiate this conjecture by proving a sharp transition at the KS bound for a restricted class of estimators, namely those that compute low-degree polynomials in the entries of the adjacency matrix. This builds on a long line of work that uses low-degree polynomials as a proxy for efficient computation, but our work is the first to establish "sharp" thresholds for the estimation (rather than detection) task. I will also discuss some unexpected phenomena that emerge when the number of communities grows with the problem size. This is based on multiple joint works with Youngtak Sohn, Byron Chin, and Elchanan Mossel.

Please report video problems to itsupport@slmath.org.

See more of our Streaming videos on our main VMath Videos page.