The method of shifted partial derivatives cannot separate the permanent from the determinant
Academic Article

 Overview

 Research

 Identity

 Additional Document Info

 View All

Overview
abstract

© 2017 American Mathematical Society. The method of shifted partial derivatives introduced A. Gupta et al. [Approaching the chasm at depth four, IEEE Comp. Soc., 2013, pp. 6573] and N. Kayal [An exponential lower bound for the sum of powers of bounded degree polynomials, ECCC 19, 2010, p. 81], was used to prove a superpolynomial lower bound on the size of depth four circuits needed to compute the permanent. We show that this method alone cannot prove that the padded permanent ℓnm permm cannot be realized inside the GLn2 orbit closure of the determinant detn when n > 2m2 +2m. Our proof relies on several simple degenerations of the determinant polynomial, Macaulay's theorem, which gives a lower bound on the growth of an ideal, and a lower bound estimate from [Approaching the chasm at depth four, IEEE Comp. Soc., 2013, pp. 6573] regarding the shifted partial derivatives of the determinant.
author list (cited authors)

Efremenko, K., Landsberg, J. M., Schenck, H., & Weyman, J.
citation count
publication date
publisher
published in
Research
keywords

Computational Complexity

Determinant

Free Resolution

Permanent
Identity
Digital Object Identifier (DOI)
Additional Document Info
start page
end page
volume
issue