Average-case Complexity for Polynomials, and All That
summary
Survey of concrete advances and limits: proves an explicit counterexample to the CHLLZ conjecture by showing TRIBES DNF retains large local correlation after log-degree polynomial approximation; obtains exact quadratic bounds (mod 3) by classifying degree-2 correlation maximizers as symmetric; clarifies generator paradigms (sum d copies of degree‑1 PRGs works for small fields but fails past degree ~log n); constructs PRGs with optimal seed length over large fields (seed ≈ d log n + log |F|) using invariant‑theory reductions and Weil bounds, with a field‑size barrier ≳ d^4.
AI-written summary · about
chapters (10)
- 0:00Introduction and announcements
- 1:09Frontier problems in complexity
- 3:50Dependencies and logical connections
- 7:23Formal definition of correlation bounds
- 12:31Local correlation and counter-examples
- 16:54Symmetric polynomials and conjectures
- 21:03Pseudorandom generators
- 23:54Fourier conjectures and majority
- 31:27Constructing pseudorandom generators
- 38:34Proof overview and decomposition
related talks
01h 11mPedagogical Talk: Failure of Low-Degree Polynomials
50mAlgorithmic Regularity for Polynomials and Applications
44mNew Techniques For Proving Fine-Grained Average-Case Hardness
11mUnderstanding Statistical-to-Computational Gaps via Low-Degree Polynomials
19mCounterexamples to the Low-Degree Conjecture
29mExtended Formulations and Information Complexity
55mLower Bounds Against PC With Extension Variables
57mStructure Of Boolean Almost Low Degree Functions On The Biased Cube