摘要：

Many classical problems in statistics, such as the planted clique problem and the spiked tensor model, are believed to exhibit the information-computation gap. The low-degree polynomial method, originated in the study of the sum-of-squares (SoS) hierarchy of convex programs, provides an understanding of computational hardness in average-case problems through low-degree likelihood ratio (LDLR).

In this talk, we will briefly introduce the low-degree polynomial method based on the note of Kunisky et al. [2019]. The low-degree polynomial method for estimation task [Schramm and Wein, 2020] will also be discussed.