Pedagogical Talk: Failure of Low-Degree Polynomials
summary
Claims that low-degree multivariate polynomials (degree ~log n) both capture common polynomial-time methods and fail where algorithms are conjecturally hard, with concrete thresholds: planted clique succeeds above k ≈ √n and advantage remains bounded below; detection advantage equals the norm of the low-degree likelihood ratio (Fourier projection), computable from orthonormal characters; recovery lower bounds use Jensen on the signal plus cumulant formulas to show trivial MMSE in the hard regime; optimization lower bounds combine stability of low-degree polynomials with an overlap-gap property.
AI-written summary · about
chapters (11)
- 0:00Introduction
- 0:55Motivation
- 2:42What is this method
- 3:34What is a low degree polynomial
- 8:04The claim
- 9:37Overview
- 10:01Detection
- 24:36Types of results
- 27:06Recap
- 31:36Recovery
- 49:31Optimization
related talks
11mUnderstanding Statistical-to-Computational Gaps via Low-Degree Polynomials
29mComputational Barriers to Estimation from Low-Degree Polynomials
01h 00mAverage-case Complexity for Polynomials, and All That
19mCounterexamples to the Low-Degree Conjecture
50mAlgorithmic Regularity for Polynomials and Applications
44mNew Techniques For Proving Fine-Grained Average-Case Hardness
29mSum Of Squares Lower Bounds Versus Low-Degree Polynomial Lower Bounds
01h 07mA Few Simple Average-Case Reduction Techniques And Their Surprising Effectiveness