THE METHOD OF SHIFTED PARTIAL DERIVATIVES CANNOT SEPARATE THE PERMANENT FROM THE DETERMINANT
Additional Document Info
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 cannot be realized inside the -orbit closure of the determinant when . 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.