
arXiv: 2311.17019
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.
This is edited part of preprint arXiv:2211.07055
FOS: Computer and information sciences, Symmetric polynomials, 68Qxx, Waring rank, Computational Complexity (cs.CC), 510, 004, Computer Science - Computational Complexity, Mathematics - Algebraic Geometry, Geometric Complexity theory, Homogeneous polynomials, Arithmetic formulas, FOS: Mathematics, F.1.3, Border complexity, Algebraic Geometry (math.AG), ddc: ddc:004
FOS: Computer and information sciences, Symmetric polynomials, 68Qxx, Waring rank, Computational Complexity (cs.CC), 510, 004, Computer Science - Computational Complexity, Mathematics - Algebraic Geometry, Geometric Complexity theory, Homogeneous polynomials, Arithmetic formulas, FOS: Mathematics, F.1.3, Border complexity, Algebraic Geometry (math.AG), ddc: ddc:004
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
