Understanding Statistical-to-Computational Gaps via Low-Degree Polynomials

on YouTube ↗11m

" summary

Low-degree polynomials act as a restricted-but-strong algorithm class and predict statistical–computational gaps: the distinguishing statistic is computable by linear algebra on the polynomial space for degree about log N, and this class captures spectral methods and AMP. For planted clique detection the brute-force threshold is clique size ~2 log2 N vs polynomial-time at ~√N. For a k×k planted submatrix with mean 10, detection succeeds by summing entries while recovery requires the leading eigenvector, showing a true detection–recovery gap.

AI-written summary · about

" chapters (8)

1. 0:00Introduction
2. 1:58The polynomial method
3. 3:28The lower bounds
4. 4:08Detection
5. 6:08Recovery
6. 8:09Analysis
7. 9:29Optimization
8. 10:18Summary

" related talks

• 01h 11mPedagogical Talk: Failure of Low-Degree PolynomialsAlex Wein · Computational Phase Transitions (Simons Institute, 2020)
• 29mComputational Barriers to Estimation from Low-Degree PolynomialsTselil Schramm · Rigorous Evidence for Information-Computation Trade-offs
• 01h 12mPedagogical Talk: Frameworks for Information-Computation TradeoffsTselil Schramm · Computational Phase Transitions (Simons Institute, 2020)
• 41mReducibility and Statistical-Computational Gaps from Secret LeakageGuy Bresler · Computational Phase Transitions (Simons Institute, 2020)
• 01h 07mA Few Simple Average-Case Reduction Techniques And Their Surprising EffectivenessGuy Bresler · Rigorous Evidence for Information-Computation Trade-offs
• 29mSum Of Squares Lower Bounds Versus Low-Degree Polynomial Lower BoundsAaron Potechin · Rigorous Evidence for Information-Computation Trade-offs
• 01h 11mStatistical Physics and Computation in High DimensionFlorent Krzakala, Lenka Zdeborova · Probability, Geometry, and Computation in High Dimensions Boot Camp (Simons Institute, Fall 2020)
• 31mStatistical Estimation on GraphsAndrea Montanari · Coding: From Practice to Theory