Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

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


Authors: Klim Efremenko, J. M. Landsberg, Hal Schenck and Jerzy Weyman
Journal: Math. Comp. 87 (2018), 2037-2045
MSC (2010): Primary 68Q17, 13D02, 14L30, 20B30
DOI: https://doi.org/10.1090/mcom/3284
Published electronically: December 4, 2017
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 ^{n-m}\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 derivatives of the determinant.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 68Q17, 13D02, 14L30, 20B30

Retrieve articles in all journals with MSC (2010): 68Q17, 13D02, 14L30, 20B30


Additional Information

Klim Efremenko
Affiliation: Computer Science Department, Ben-Gurion University, Beer-Sheva, 84105 Israel
Email: klimefrem@gmail.com

J. M. Landsberg
Affiliation: Department of Mathematics, Texas A&M University, College Station, Texas 77843
Email: jml@math.tamu.edu

Hal Schenck
Affiliation: Department of Mathematics, Iowa State University, Ames, Iowa 50011
Email: hschenck@iastate.edu

Jerzy Weyman
Affiliation: Department of Mathematics, University of Connecticut, Storrs, Connecticut 06269
Email: jerzy.weyman@gmail.com

DOI: https://doi.org/10.1090/mcom/3284
Keywords: Computational complexity, free resolution, determinant, permanent
Received by editor(s): September 7, 2016
Received by editor(s) in revised form: November 11, 2016, December 14, 2016, and February 22, 2017
Published electronically: December 4, 2017
Additional Notes: The first author was supported in part by European Community Seventh Framework Programme (FP7/2007-2013) under grant agreement number 257575.
The second author was supported by NSF DMS-1405348
The third author was supported by NSF DMS-1312071
The fourth author was supported by NSF DMS-1400740
Article copyright: © Copyright 2017 American Mathematical Society

American Mathematical Society