Pedagogical Talk: Frameworks for Information-Computation Tradeoffs

on YouTube ↗01h 12m

" summary

Shows concrete reductions: if a degree-d sum-of-squares relaxation distinguishes a noise‑robust planted hypothesis, then an explicit degree‑O(d) spectral test (matrix whose entries are degree‑d polynomials of the data, threshold top eigenvalue) also distinguishes the original model, nonconstructively, with runtime roughly n^{O(d)}. Also proves an almost‑equivalence between low‑degree polynomials and the statistical query (V‑stat) model, letting existing lower bounds transfer (tensor PCA, sparse PCA, Gaussian mixtures, robust mean, variants of planted clique); exceptions arise when single‑sample likelihoods dominate.

AI-written summary · about

" chapters (17)

1. 0:00Introduction to the talk
2. 1:21Statistical phase transitions
3. 3:57Planted clique problem
4. 5:51Complexity and reductions
5. 7:54Restricted computational models
6. 11:31The case for algorithmic equivalence
7. 15:30Recent theoretical advancements
8. 20:26Sum of squares vs. spectral methods
9. 24:24Equivalence theorem
10. 32:07Audience Q&A session
11. 37:14Role of low-degree polynomials
12. 40:35SQ vs. low-degree polynomials
13. 44:04Defining statistical query access
14. 47:10Low-degree test definitions
15. 51:28Model mismatch and reduction
16. 55:07Main theorem and implications
17. 59:19Closing remarks

" related talks

• 11mUnderstanding Statistical-to-Computational Gaps via Low-Degree PolynomialsAlex Wein · Meet the Fellows Welcome Event
• 01h 07mA Few Simple Average-Case Reduction Techniques And Their Surprising EffectivenessGuy Bresler · Rigorous Evidence for Information-Computation Trade-offs
• 29mComputational Barriers to Estimation from Low-Degree PolynomialsTselil Schramm · Rigorous Evidence for Information-Computation Trade-offs
• 19mCounterexamples to the Low-Degree ConjectureAlexander S Wein, Justin Holmgren · ITCS 2021
• 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)
• 48mComputational-Statistical Tradeoffs in Robust High-Dimensional EstimationIlias Diakonikolas · Robust and High-Dimensional Statistics (Simons Institute workshop, 2018)
• 01h 04mAlgorithmic High Dimensional Robust Statistics IIIlias Diakonikolas · Foundations of Data Science Boot Camp 2018