Description:

Phase transitions in estimation with low-degree polynomials

Youngtak Sohn, Assistant Professor, Applied Mathematics, Brown University

Abstract: High-dimensional planted problems, such as finding a hidden dense subgraph within a random graph, often exhibit a gap between statistical and computational feasibility.  While recovering the hidden structure may be statistically possible, it is conjectured to be computationally intractable in certain parameter regimes.  A powerful approach to understanding this hardness involves proving lower bounds on the efficacy of low-degree polynomial algorithms. In this talk, I will introduce the low-degree polynomial framework and explain how it captures key features of algorithmic hardness. I will then discuss recent progress on understanding computational barriers in community detection under the Stochastic Block Model with many communities. This is joint work with Byron Chin, Elchanan Mossel, and Alex Wein.