Families of Anticommuting Matrices and the Sum of Squares Problem
summary
Question asks how many squares K write sum_{i=1}^n x_i^2 y_i^2 as sum of K bilinear squares; trivial bounds give n ≤ s(n) ≤ n^2 and best known constructive upper bound is about n^2 / log n. Conjecture links this to families of n×n complex matrices with E_i E_j = -E_j E_i: claim is that the sum of ranks of E_i^2 is O(n log n), which would force s(n) to be superlinear. Known facts: full‑rank anticommuting families satisfy K ≤ 2 log2 n, Hurwitz gives equality s(n)=n only for n = 1,2,4,8, and the main hard case is nilpotent E_i.
AI-written summary · about
chapters (7)
- 0:00Sum of squares problem
- 3:16Bounds on sum of squares
- 8:49Historical identities
- 12:24Anticommuting matrices link
- 19:10Anticommuting matrices conjectures
- 23:35Open questions on anticommuting
- 26:46Computational challenges
related talks
01h 57mFun with Lattices
25mThe Whole is Greater than the Sum of its Parts: Linear Garbling and Applications
01h 06mObfuscation: Past, Present, and Possible Futures
27mSparsity and Privacy in Distributed Matrix Multiplication
20mSNARKs from the sum-check protocol
55mNP-hardness of Nuclear Norms for Tensors
01h 04mUsing Lattices for Cryptanalysis
44mHow Robust are Linear Sketches to Adaptive Inputs?