Time：Wednesday, Sept.16, 14:00-15:00 Venue: Room 104
1. 主讲人介绍
Songtao Mao(毛松涛) is a Ph.D. student in Computer Science at Johns Hopkins University, advised by Professor Xin Li. He received his bachelor’s degree in mathematics from Zhiyuan College at Shanghai Jiao Tong University. His research interests include pseudorandomness, coding theory, average-case complexity, and cryptography.
2. 讲座介绍
Title: Low-Degree Conjecture
Abstract: The low-degree conjecture is a widely used and powerful framework for predicting statistical–computational gaps across average-case complexity, high-dimensional statistics, learning theory, and cryptography. It asserts that, for certain hypothesis-testing problems, low-degree polynomial statistics capture the distinguishing power of polynomial-time algorithms. This heuristic successfully reproduces known computational thresholds in many canonical problems, including planted clique, noisy k-XOR, tensor PCA, community detection, and random constraint satisfaction problems. However, a series of recent works has ultimately disproved the conjecture.
In this talk, I will introduce the background and formulation of the low-degree method and the low-degree conjecture, and explain why they became central tools for studying average-case hardness. I will then present several recent counterexamples, which have prompted researchers to reevaluate the limitations of existing algorithmic paradigms and motivated the search for more accurate characterizations of efficient computation.
