Geometric complexity theory for product-plus-power
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910971536080896 |
|---|---|
| author | Dutta, Pranjal Gesmundo, Fulvio Ikenmeyer, Christian Jindal, Gorav Lysikov, Vladimir |
| author_facet | Dutta, Pranjal Gesmundo, Fulvio Ikenmeyer, Christian Jindal, Gorav Lysikov, Vladimir |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2211_07055 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Geometric complexity theory for product-plus-power Dutta, Pranjal Gesmundo, Fulvio Ikenmeyer, Christian Jindal, Gorav Lysikov, Vladimir Computational Complexity Algebraic Geometry 68W30, 14-XX, 05E10 F.1.3 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. |
| title | Geometric complexity theory for product-plus-power |
| topic | Computational Complexity Algebraic Geometry 68W30, 14-XX, 05E10 F.1.3 |
| url | https://arxiv.org/abs/2211.07055 |