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

•
• Overview
•
• Research
•
•
• View All
•

### abstract

• The method of shifted partial derivatives introduced A. Gupta et al.[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 $\ell^{nm}\mathrm {perm} _m$ cannot be realized inside the $GL_ {n^ 2}$-orbit closure of the determinant $\mathrm {det} _n$ when $n> 2m^ 2+ 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. 65-73] regarding the shifted partial …

### publication date

• January 1, 2017