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

abstract

  • The method of shifted partial derivatives introduced A. Gupta etal. [Approaching the chasm at depth four, IEEE Comp. Soc., 2013, pp.65-73] 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 super-polynomial 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 n m p e r m m ell ^{n-m}mathrm {perm}_m cannot be realized inside the G L n 2 GL_{n^2} -orbit closure of the determinant d e t n mathrm {det}_n when n > 2 m 2 + 2 m n>2m^2+2m . Our proof relies on several simple degenerations of the determinant polynomial, Macaulays 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.65-73] regarding the shifted partial derivatives of the determinant.

published proceedings

  • Mathematics of Computation

author list (cited authors)

  • Efremenko, K., Landsberg, J., Schenck, H., & Weyman, J.

citation count

  • 3

complete list of authors

  • Efremenko, Klim||Landsberg, J||Schenck, Hal||Weyman, Jerzy

publication date

  • December 2017