Border complexity via elementary symmetric polynomials
share
In (ToCT'20) Kumar surprisingly proved that every polynomial can be approximated as a sum of a constant and a product of linear polynomials. In this work, we prove the converse of Kumar's result which ramifies in a surprising new formulation of Waring rank and border Waring rank. From this conclusion, we branch out into two different directions, and implement the geometric complexity theory (GCT) approach in two different settings. In the first direction, we study the orbit closure of the product-plus-power polynomial, determine its stabilizer, and determine the properties of its boundary points. We also connect its fundamental invariant to the Alon-Tarsi conjecture on Latin squares, and prove several exponential separations between related polynomials contained in the affine closure of product-plus-product polynomials. We fully implement the GCT approach and obtain several equations for the product-plus-power polynomial from its symmetries via representation theoretic multiplicity obstructions. In the second direction, we demonstrate that the non-commutative variant of Kumar's result is intimately connected to the constructions of Ben-Or and Cleve (SICOMP'92), and Bringmann, Ikenmeyer, Zuiddam (JACM'18), which describe algebraic formulas in terms of iterated matrix multiplication. From this we obtain that a variant of the elementary symmetric polynomial is complete for V3F, a large subclass of VF, under homogeneous border projections. In the regime of quasipolynomial complexity, our polynomial has the same power as the determinant or as arbitrary circuits, i.e., VQP. This is the first completeness result under homogeneous projections for a subclass of VBP. Such results are required to set up the GCT approach in a way that avoids the no-go theorems of Bürgisser, Ikenmeyer, Panova (JAMS'19). ...
READ FULL TEXT