Homogeneous Algebraic Complexity Theory and Algebraic Formulas
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915008335577088 |
|---|---|
| author | Dutta, Pranjal Gesmundo, Fulvio Ikenmeyer, Christian Jindal, Gorav Lysikov, Vladimir |
| author_facet | Dutta, Pranjal Gesmundo, Fulvio Ikenmeyer, Christian Jindal, Gorav Lysikov, Vladimir |
| contents | We study algebraic complexity classes and their complete polynomials under \emph{homogeneous linear} projections, not just under the usual affine linear projections that were originally introduced by Valiant in 1979. These reductions are weaker yet more natural from a geometric complexity theory (GCT) standpoint, because the corresponding orbit closure formulations do not require the padding of polynomials. We give the \emph{first} complete polynomials for VF, the class of sequences of polynomials that admit small algebraic formulas, under homogeneous linear projections: The sum of the entries of the non-commutative elementary symmetric polynomial in 3 by 3 matrices of homogeneous linear forms.
Even simpler variants of the elementary symmetric polynomial are hard for the topological closure of a large subclass of VF: the sum of the entries of the non-commutative elementary symmetric polynomial in 2 by 2 matrices of homogeneous linear forms, and homogeneous variants of the continuant polynomial (Bringmann, Ikenmeyer, Zuiddam, JACM '18). This requires a careful study of circuits with arity-3 product gates. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2311_17019 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Homogeneous Algebraic Complexity Theory and Algebraic Formulas Dutta, Pranjal Gesmundo, Fulvio Ikenmeyer, Christian Jindal, Gorav Lysikov, Vladimir Computational Complexity Algebraic Geometry 68Qxx F.1.3 We study algebraic complexity classes and their complete polynomials under \emph{homogeneous linear} projections, not just under the usual affine linear projections that were originally introduced by Valiant in 1979. These reductions are weaker yet more natural from a geometric complexity theory (GCT) standpoint, because the corresponding orbit closure formulations do not require the padding of polynomials. We give the \emph{first} complete polynomials for VF, the class of sequences of polynomials that admit small algebraic formulas, under homogeneous linear projections: The sum of the entries of the non-commutative elementary symmetric polynomial in 3 by 3 matrices of homogeneous linear forms. Even simpler variants of the elementary symmetric polynomial are hard for the topological closure of a large subclass of VF: the sum of the entries of the non-commutative elementary symmetric polynomial in 2 by 2 matrices of homogeneous linear forms, and homogeneous variants of the continuant polynomial (Bringmann, Ikenmeyer, Zuiddam, JACM '18). This requires a careful study of circuits with arity-3 product gates. |
| title | Homogeneous Algebraic Complexity Theory and Algebraic Formulas |
| topic | Computational Complexity Algebraic Geometry 68Qxx F.1.3 |
| url | https://arxiv.org/abs/2311.17019 |