Volume 15 (2019)
Article 3 pp. 1-24
Explicit Polynomial Sequences with Maximal Spaces of Partial Derivatives and a Question of K. Mulmuley
Received: June 18, 2017
Revised: December 31, 2018
Published: September 12, 2019
Revised: December 31, 2018
Published: September 12, 2019
Keywords: computational complexity, Waring border rank, shifted partial derivatives, Koszul flattening
Categories: computational complexity, Waring border rank, shifted partial derivatives, Koszul flattening
ACM Classification: F.1.3
AMS Classification: 68Q15, 15A69
Abstract: [Plain Text Version]
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.
Licensed under a Creative Commons Attribution License (CC-BY)