True Complexity of Multilinear Systems

on YouTube ↗01h 01m

" summary

Proves two concrete things for six forms in three variables: first, there exist systems over Fp where the counting average stays large while all U2 norms stay tiny, so error bounds must worsen with the integer coefficients (bad examples explicitly constructed); second, there is an explicit Cauchy‑Schwarz machine — an algorithmic sequence of many Cauchy‑Schwarz steps guided by a projective‑plane/Möbius geometry — that yields a polynomial bound (but with constants that grow rapidly with coefficient size and require many iterations, often impractically large).

AI-written summary · about

" chapters (7)

1. 0:00Introduction
2. 10:37Cauchy-Schwarz complexity
3. 21:51True complexity vs bounds
4. 32:36Six forms in three variables
5. 40:35Proof strategy
6. 53:30Geometric interpretation
7. 1:00:15Q&A

" related talks

• 55mNon-commutative ComputationAvi Wigderson · Neo-Classical Methods in Discrete Analysis 2013
• 39mStructure of the Fourier Spectrum of Boolean Functions and ComplexityBen Lee Volk · Neo-Classical Methods in Discrete Analysis 2013
• 01h 04mExplicit SoS Lower Bounds from (Small-Set) High Dimensional ExpandersMax Hopkins · Beyond the Boolean Cube 2023
• 55mLower Bounds Against PC With Extension VariablesRussell Impagliazzo · Proof Complexity and Meta-Mathematics 2023
• 47mHardness Amplification and the Approximate Degree of Constant-Depth CircuitsJustin Thaler · Neo-Classical Methods in Discrete Analysis 2013
• 57mComputing Multiplicities of Lie Group RepresentationsMatthias Christandl · Geometric Complexity Theory 2014
• 26mOn the Intersection of a Sparse Curve and a Low-degree Curve: A Polynomial Version of the Lost TheorSébastien Tavenas · Solving Polynomial Equations (Simons Institute, 2014)
• 29mApproximating the Permanent of Positive Semidefinite MatricesNima Anari · Discrete Optimization via Continuous Relaxation