Explicit Polynomial Sequences with Maximal Spaces of Partial Derivatives and a Question of K. Mulmuley

by Fulvio Gesmundo and Joseph M. Landsberg

Theory of Computing, Volume 15(3), pp. 1-24, 2019

Bibliography with links to cited articles

[1]   Otto Biermann: Über näherungsweise Cubaturen. Monatshefte für Mathematik und Physik, 14(1):211–225, 1903. [doi:10.1007/BF01706869]

[2]   Weronika Buczyńska and Jarosłav Buczyński: Secant varieties to high degree Veronese reembeddings, catalecticant matrices and smoothable Gorenstein schemes. J. Algebraic Geom., 23(1):63–90, 2014. [doi:10.1090/S1056-3911-2013-00595-0, arXiv:1012.3563]

[3]   Peter Bürgisser, Christian Ikenmeyer, and Greta Panova: No occurrence obstructions in geometric complexity theory. J. Amer. Math. Soc., 32(1):163–193, 2019. [doi:10.1090/jams/908, arXiv:1604.06431]

[4]   Xi Chen, Neeraj Kayal, and Avi Wigderson: Partial derivatives in arithmetic complexity and beyond. Found. Trends Theor. Comput. Sci., 6(1-2):1–138, 2010. [doi:10.1561/0400000043]

[5]   Klim Efremenko, Ankit Garg, Rafael Oliveira, and Avi Wigderson: Barriers for rank methods in arithmetic complexity. In Proc. 9th Innovations in Theoret. Comp. Sci. conf. (ITCS’18), pp. 1:1–1:19. Leibniz Zentrum für Informatik, 2018. [doi:10.4230/LIPIcs.ITCS.2018.1, arXiv:1710.09502]

[6]   Klim Efremenko, Joseph M. Landsberg, Hal Schenck, and Jerzy Weyman: The method of shifted partial derivatives cannot separate the permanent from the determinant. Mathematics of Computation, 87(312):2037–2045, 2018. [doi:10.1090/mcom/3284, arXiv:1609.02103]

[7]   Hervé Fournier, Nutan Limaye, Meena Mahajan, and Srikanth Srinivasan: The shifted partial derivative complexity of elementary symmetric polynomials. Theory of Computing, 13(9):1–34, 2017. Preliminary version in MFCS’15. [doi:10.4086/toc.2017.v013a009]

[8]   William Fulton and Joe Harris: Representation Theory: A First Course. Springer, 1991. [doi:10.1007/978-1-4612-0979-9]

[9]   Maciej Gałązka: Vector bundles give equations of cactus varieties. Lin. Alg. Appl., 521:254–262, 2017. [doi:10.1016/j.laa.2016.12.005, arXiv:1605.08005]

[10]   Fulvio Gesmundo, Christian Ikenmeyer, and Greta Panova: Geometric complexity theory and matrix powering. Diff. Geom. Appl., 55:106–127, 2017. [doi:10.1016/j.difgeo.2017.07.001, arXiv:1611.00827]

[11]   Ira Gessel and Gérard Viennot: Binomial determinants, paths, and hook length formulae. Adv. in Math., 58(3):300–321, 1985. [doi:10.1016/0001-8708(85)90121-5]

[12]   Daniel R. Grayson and Mike E. Stillman: Macaulay2, a software system for research in algebraic geometry. Available here.

[13]   Edward L. Green: Complete intersections and Gorenstein ideals. J. Algebra, 52(1):264–273, 1978. [doi:10.1016/0021-8693(78)90274-0]

[14]   Ankit Gupta, Pritish Kamath, Neeraj Kayal, and Ramprasad Saptharishi: Arithmetic circuits: A chasm at depth 3. SIAM J. Comput., 45(3):1064–1079, 2016. Preliminary version in FOCS’13. [doi:10.1137/140957123]

[15]   Antony Iarrobino and Jacques Emsalem: Some zero-dimensional generic singularities; finite algebras having small tangent space. Compositio Math., 36(2):145–188, 1978. NUMDAM.

[16]   Antony Iarrobino and Vassil Kanev: Power Sums, Gorenstein Algebras, and Determinantal Loci. Springer, 1999. [doi:10.1007/BFb0093426]

[17]   Christian Ikenmeyer and Greta Panova: Rectangular Kronecker coefficients and plethysms in geometric complexity theory. Adv. Math., 319:40–66, 2017. Preliminary version in FOCS’16. [doi:10.1016/j.aim.2017.08.024, arXiv:1512.03798]

[18]   Neeraj Kayal: An exponential lower bound for the sum of powers of bounded degree polynomials. Electr. Coll. Comp. Compl. (ECCC), 81, 2012.

[19]   Joseph M. Landsberg: Tensors: Geometry and Applications. Amer. Math. Soc., 2012. [doi:10.1090/gsm/128]

[20]   Joseph M. Landsberg: Geometry and Complexity Theory. Cambridge University Press, 2017. [doi:10.1017/9781108183192]

[21]   Joseph M. Landsberg and Giorgio Ottaviani: Equations for secant varieties of Veronese and other varieties. Annali di Matematica Pura ed Applicata, 192(4):569–606, 2013. [doi:10.1007/s10231-011-0238-6, arXiv:1111.4567]

[22]   Hwangrae Lee: Power sum decompositions of elementary symmetric polynomials. Lin. Alg. Appl., 492:89–97, 2016. [doi:10.1016/j.laa.2015.11.018, arXiv:1508.05235]

[23]   M. Stuart Lynn: On the Schur product of H-matrices and non-negative matrices, and related inequalities. Math. Proc. Cambridge Phil. Soc., 60(3):425–431, 1964. [doi:10.1017/S0305004100037932]

[24]   Noam Nisan: Lower bounds for non-commutative computation. In Proc. 23rd STOC, pp. 410–418. ACM Press, 1991. [doi:10.1145/103418.103462]

[25]   Noam Nisan and Avi Wigderson: Lower bounds on arithmetic circuits via partial derivatives. Comput. Complexity, 6(3):217–234, 1996. Preliminary version in FOCS’95. [doi:10.1007/BF01294256]

[26]   Luke Oeding and Giorgio Ottaviani: Eigenvectors of tensors and algorithms for Waring decomposition. J. Symb. Comput., 54:9–35, 2013. [doi:10.1016/j.jsc.2012.11.005, arXiv:1103.0203]

[27]   Viktor V. Prasolov: Problems and Theorems in Linear Algebra. Amer. Math. Soc., 1994. [doi:10.1090/mmono/134]

[28]   Bruce Reznick: Sums of even powers of real linear forms. Mem. Amer. Math. Soc., 96(463), 1992. [doi:10.1090/memo/0463]

[29]   Amir Shpilka and Avi Wigderson: Depth-3 arithmetic circuits over fields of characteristic zero. Comput. Complexity, 10(1):1–27, 2001. Preliminary version in CCC’99. [doi:10.1007/PL00001609]

[30]   Richard P. Stanley: Hilbert functions of graded algebras. Adv. in Math., 28(1):57–83, 1978. [doi:10.1016/0001-8708(78)90045-2]

[31]   Noah Stein: Full rank submatrices of positive semidefinite matrix, 1917. MathOverflow.

[32]   James J. Sylvester: On the principles of the calculus of forms. Cambridge and Dublin Math. J., 7:52–97, 1852.