The low-degree method is a central tool for studying statistical–computational gaps in average-case complexity and high-dimensional statistics. It provides a unified framework and has successfully guided algorithm design and predicted computational lower bound for many problems. This led to the low-degree conjecture, which proposes that, under suitable assumptions, hardness against low-degree polynomial statistics implies hardness for efficient algorithms.

 

In this talk, I will introduce the low-degree method through our recent work on noisy k-XOR and planted clique problems and illustrate how to design informative polynomial statistics and implement the algorithm using color-coding and dynamic programming. I will then discuss the low-degree conjecture, its motivation, and its use in predicting computational lower bounds.

Songtao Mao is a Ph.D. student in Computer Science at Johns Hopkins University, working on the computational complexity problems in statistics and cryptography. He received the bachelor’s degree in mathematics from Zhiyuan at SJTU.