Theory of Computing
-------------------
Title : Explicit Polynomial Sequences with Maximal Spaces of Partial Derivatives and a Question of K. Mulmuley
Authors : Fulvio Gesmundo and Joseph M. Landsberg
Volume : 15
Number : 3
Pages : 1-24
URL : https://theoryofcomputing.org/articles/v015a003
Abstract
--------
We answer a question of K. Mulmuley. Efremenko et al. (Math. Comp.,
2018) have shown that the method of shifted partial derivatives cannot
be used to separate the padded permanent from the determinant.
Mulmuley asked if this "no-go" result could be extended to a model
without padding. We prove this is indeed the case using the iterated
matrix multiplication polynomial. We also provide several examples of
polynomials with maximal space of partial derivatives, including the
complete symmetric polynomials. We apply Koszul flattenings to these
polynomials to have the first explicit sequence of polynomials with
symmetric border rank lower bounds higher than the bounds attainable
via partial derivatives.