For fixed degree d, strength and partition rank over any field are bounded by O(r^{d-1}) (plus a log factor on finite fields) in terms of their border rank analogues.
Geometric complexity theory for product-plus-power
1 Pith paper cite this work. Polarity classification is still indexing.
abstract
According to Kumar's recent surprising result (ToCT'20), a small border Waring rank implies that the polynomial can be approximated as a sum of a constant and a small product of linear polynomials. We prove the converse of Kumar's result and establish a tight connection between border Waring rank and the model of computation in Kumar's result. In this way, we obtain a new formulation of border Waring rank, up to a factor of the degree. We connect this new formulation to the orbit closure problem of the product-plus-power polynomial. We study this orbit closure from two directions: 1. We deborder this orbit closure and some related orbit closures, i.e., prove all points in the orbit closure have small non-border algebraic branching programs. 2. We fully implement the geometric complexity theory approach against the power sum by generalizing the ideas of Ikenmeyer-Kandasamy (STOC'20) to this new orbit closure. In this way, we obtain new multiplicity obstructions that are constructed from just the symmetries of the polynomials.
fields
math.AG 1years
2025 1verdicts
CONDITIONAL 1representative citing papers
citing papers explorer
-
Strength and partition rank under limits and field extensions
For fixed degree d, strength and partition rank over any field are bounded by O(r^{d-1}) (plus a log factor on finite fields) in terms of their border rank analogues.