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.

Time

Wednesday, Sept. 16, 14:00 - 15:00

Speaker

Songtao Mao(毛松涛), Johns Hopkins University

Room

Room 104