Algorithmic Regularity for Polynomials and Applications

on YouTube ↗50m

" summary

Randomized polynomial-time algorithms find an explicit degree-(D−1) polynomial factor that exactly generates any biased degree-D polynomial over high-characteristic fields, by estimating Gowers U^{k} norm values, refining factors to gamma-uniformity, and using Goldreich-Levin style search for large correlations. The procedure outputs the factor (and runs in roughly n^D time), and it enables decoding Reed–Muller codes beyond the usual list-decoding radius when the received word is a higher-degree polynomial.

AI-written summary · about

" chapters (22)

1. 0:00Intro
2. 2:54Szemerédi Regularity Lemma
3. 4:58Pseudorandomness for Functions over Finite Fields
4. 6:48Pseudorandomness against linear phase polynomials
5. 7:56Simple Decomposition Theorem
6. 9:53Higher Degree
7. 11:41Higher Order Fourier Analysis
8. 14:59Polynomial factors
9. 15:35Regularity of Polynomials
10. 16:57Near Orthogonality and Regularity
11. 19:32Refining to Regularity
12. 21:52Decomposition for Polynomials
13. 26:20Towards an algorithmic regularity lemma
14. 27:31First attempt
15. 28:36Unbiased Refinement (Regularity Lemma)
16. 29:22Gowers uniformity norm
17. 30:59Direct and Inverse Theorems
18. 33:17Main Technical Lemmas
19. 36:07Gowers Inverse Theorem for Polynomials
20. 38:02Reed-Muller Code
21. 39:14Decoding from Structured Noise
22. 45:19Conclusion

" related talks

• 01h 00mAverage-case Complexity for Polynomials, and All ThatEmanuele Viola · Lower Bounds, Learning, and Average-Case Complexity
• 01h 11mPedagogical Talk: Failure of Low-Degree PolynomialsAlex Wein · Computational Phase Transitions (Simons Institute, 2020)
• 11mUnderstanding Statistical-to-Computational Gaps via Low-Degree PolynomialsAlex Wein · Meet the Fellows Welcome Event
• 19mCounterexamples to the Low-Degree ConjectureAlexander S Wein, Justin Holmgren · ITCS 2021
• 57mStructure Of Boolean Almost Low Degree Functions On The Biased CubeYuval Filmus · Structural Results 2023
• 44mNew Techniques For Proving Fine-Grained Average-Case HardnessAndrea Lincoln · Rigorous Evidence for Information-Computation Trade-offs
• 29mComputational Barriers to Estimation from Low-Degree PolynomialsTselil Schramm · Rigorous Evidence for Information-Computation Trade-offs
• 27mWeak Decoupling, Polynomial Folds, and Approximate Optimization over the SphereVijay Bhattiprolu · Hierarchies, Extended Formulations and Matrix-Analytic Techniques (2017)