Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

Request Permissions   Purchase Content 
 
 

 

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.
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?)

  • [1] M. Agrawal and V. Vinay, Arithmetic circuits: A chasm at depth four, In Proc. 49th IEEE Symposium on Foundations of Computer Science (2008), 67-75.
  • [2] Richard P. Brent, The parallel evaluation of general arithmetic expressions, J. Assoc. Comput. Mach. 21 (1974), 201-206. MR 0660280, https://doi.org/10.1145/321812.321815
  • [3] K. Efremenko, J. M. Landsberg, H. Schenck, and J. Weyman, On minimal free resolutions of sub-permanents and other ideals arising in complexity theory, preprint (2016). To appear in J. Algebra.
  • [4] Gerd Gotzmann, Eine Bedingung für die Flachheit und das Hilbertpolynom eines graduierten Ringes, Math. Z. 158 (1978), no. 1, 61-70 (German). MR 0480478, https://doi.org/10.1007/BF01214566
  • [5] Mark L. Green, Generic initial ideals, Six lectures on commutative algebra (Bellaterra, 1996) Progr. Math., vol. 166, Birkhäuser, Basel, 1998, pp. 119-186. MR 1648665
  • [6] Joshua A. Grochow, Unifying known lower bounds via geometric complexity theory, Comput. Complexity 24 (2015), no. 2, 393-475. MR 3349809, https://doi.org/10.1007/s00037-015-0103-x
  • [7] Ankit Gupta, Pritish Kamath, Neeraj Kayal, and Ramprasad Saptharishi, Approaching the chasm at depth four, 2013 IEEE Conference on Computational Complexity--CCC 2013, IEEE Computer Soc., Los Alamitos, CA, 2013, pp. 65-73. MR 3306975, https://doi.org/10.1109/CCC.2013.16
  • [8] A. Gupta, P. Kamath, N. Kayal, and R. Saptharishi, Arithmetic circuits: A chasm at depth three, Electronic Colloquium on Computational Complexity (ECCC) 20 (2013), p. 26.
  • [9] N. Kayal, An exponential lower bound for the sum of powers of bounded degree polynomials, Electronic Colloquium on Computational Complexity (ECCC) 19 (2012), p. 81.
  • [10] Pascal Koiran, Arithmetic circuits: the chasm at depth four gets wider, Theoret. Comput. Sci. 448 (2012), 56-65. MR 2943969, https://doi.org/10.1016/j.tcs.2012.03.041
  • [11] J. M. Landsberg and Giorgio Ottaviani, Equations for secant varieties of Veronese and other varieties, Ann. Mat. Pura Appl. (4) 192 (2013), no. 4, 569-606. MR 3081636, https://doi.org/10.1007/s10231-011-0238-6
  • [12] Noam Nisan and Avi Wigderson, Lower bounds on arithmetic circuits via partial derivatives, Comput. Complexity 6 (1996/97), no. 3, 217-234. MR 1486927, https://doi.org/10.1007/BF01294256
  • [13] J. J. Sylvester, On the principles of the calculus of forms, Cambridge and Dublin Mathematical Journal (1852), 52-97.
  • [14] Sébastien Tavenas, Improved bounds for reduction to depth 4 and depth 3, Inform. and Comput. 240 (2015), 2-11. MR 3303254, https://doi.org/10.1016/j.ic.2014.09.004
  • [15] L. G. Valiant, Completeness classes in algebra, Conference Record of the Eleventh Annual ACM Symposium on Theory of Computing (Atlanta, GA, 1979) ACM, New York, 1979, pp. 249-261. MR 564634

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