No occurrence obstructions in geometric complexity theory
HTML articles powered by AMS MathViewer
- by Peter Bürgisser, Christian Ikenmeyer and Greta Panova
- J. Amer. Math. Soc. 32 (2019), 163-193
- DOI: https://doi.org/10.1090/jams/908
- Published electronically: October 4, 2018
- HTML | PDF | Request permission
Abstract:
The permanent versus determinant conjecture is a major problem in complexity theory that is equivalent to the separation of the complexity classes $\mathrm {VP}_{\mathrm {ws}}$ and $\mathrm {VNP}$. In 2001 Mulmuley and Sohoni suggested studying a strengthened version of this conjecture over complex numbers that amounts to separating the orbit closures of the determinant and padded permanent polynomials. In that paper it was also proposed to separate these orbit closures by exhibiting occurrence obstructions, which are irreducible representations of $\mathrm {GL}_{n^2}(\mathbb {C})$, which occur in one coordinate ring of the orbit closure, but not in the other. We prove that this approach is impossible. However, we do not rule out the general approach to the permanent versus determinant problem via multiplicity obstructions as proposed by Mulmuley and Sohoni in 2001.References
- N. Alon and M. Tarsi, Colorings and orientations of graphs, Combinatorica 12 (1992), no. 2, 125–134. MR 1179249, DOI 10.1007/BF01204715
- Jarod Alper, Tristram Bogart, and Mauricio Velasco, A lower bound for the determinantal complexity of a hypersurface, Found. Comput. Math. 17 (2017), no. 3, 829–836. MR 3648107, DOI 10.1007/s10208-015-9300-x
- Peter Bürgisser, Completeness and reduction in algebraic complexity theory, Algorithms and Computation in Mathematics, vol. 7, Springer-Verlag, Berlin, 2000. MR 1771845, DOI 10.1007/978-3-662-04179-6
- Peter Bürgisser, Cook’s versus Valiant’s hypothesis, Theoret. Comput. Sci. 235 (2000), no. 1, 71–88. Selected papers in honor of Manuel Blum (Hong Kong, 1998). MR 1765966, DOI 10.1016/S0304-3975(99)00183-8
- Peter Bürgisser, The complexity of factors of multivariate polynomials, Found. Comput. Math. 4 (2004), no. 4, 369–396. MR 2097213, DOI 10.1007/s10208-002-0059-5
- P. Bürgisser, Permanent versus determinant, obstructions, and Kronecker coefficients, Sém. Lothar. Combin., 75 (2015); arXiv:1511.08113 (2015).
- Peter Bürgisser, Matthias Christandl, and Christian Ikenmeyer, Even partitions in plethysms, J. Algebra 328 (2011), 322–329. MR 2745569, DOI 10.1016/j.jalgebra.2010.10.031
- Peter Bürgisser, Matthias Christandl, and Christian Ikenmeyer, Nonvanishing of Kronecker coefficients for rectangular shapes, Adv. Math. 227 (2011), no. 5, 2082–2091. MR 2803795, DOI 10.1016/j.aim.2011.04.012
- Peter Bürgisser, Christian Ikenmeyer, and Jesko Hüttenhain, Permanent versus determinant: not via saturations, Proc. Amer. Math. Soc. 145 (2017), no. 3, 1247–1258. MR 3589323, DOI 10.1090/proc/13310
- Peter Bürgisser and Christian Ikenmeyer, Fundamental invariants of orbit closures, J. Algebra 477 (2017), 390–434. MR 3614157, DOI 10.1016/j.jalgebra.2016.12.035
- Peter Bürgisser, Christian Ikenmeyer, and Greta Panova, No occurrence obstructions in geometric complexity theory, 57th Annual IEEE Symposium on Foundations of Computer Science—FOCS 2016, IEEE Computer Soc., Los Alamitos, CA, 2016, pp. 386–395. MR 3631001
- Peter Bürgisser, J. M. Landsberg, Laurent Manivel, and Jerzy Weyman, An overview of mathematical issues arising in the geometric complexity theory approach to $\textrm {VP}\neq \textrm {VNP}$, SIAM J. Comput. 40 (2011), no. 4, 1179–1209. MR 2861717, DOI 10.1137/090765328
- Jin-Yi Cai, Xi Chen, and Dong Li, Quadratic lower bound for permanent vs. determinant in any characteristic, Comput. Complexity 19 (2010), no. 1, 37–56. MR 2601194, DOI 10.1007/s00037-009-0284-2
- Christophe Carré and Jean-Yves Thibon, Plethysm and vertex operators, Adv. in Appl. Math. 13 (1992), no. 4, 390–403. MR 1190119, DOI 10.1016/0196-8858(92)90018-R
- Arthur Cayley, The collected mathematical papers. Volume 2, Cambridge Library Collection, Cambridge University Press, Cambridge, 2009. Reprint of the 1889 original. MR 2866114
- Matthias Christandl, Brent Doran, and Michael Walter, Computing multiplicities of Lie group representations, 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science—FOCS 2012, IEEE Computer Soc., Los Alamitos, CA, 2012, pp. 639–648. MR 3186652
- Igor Dolgachev, Lectures on invariant theory, London Mathematical Society Lecture Note Series, vol. 296, Cambridge University Press, Cambridge, 2003. MR 2004511, DOI 10.1017/CBO9780511615436
- William Fulton and Joe Harris, Representation theory, Graduate Texts in Mathematics, vol. 129, Springer-Verlag, New York, 1991. A first course; Readings in Mathematics. MR 1153249, DOI 10.1007/978-1-4612-0979-9
- Fulvio Gesmundo, Christian Ikenmeyer, and Greta Panova, Geometric complexity theory and matrix powering, Differential Geom. Appl. 55 (2017), 106–127. MR 3724215, DOI 10.1016/j.difgeo.2017.07.001
- B. Grenet, An upper bound for the permanent versus determinant problem, Theory of Computing (to appear).
- Roger Howe, $(\textrm {GL}_n,\textrm {GL}_m)$-duality and symmetric plethysm, Proc. Indian Acad. Sci. Math. Sci. 97 (1987), no. 1-3, 85–109 (1988). MR 983608, DOI 10.1007/BF02837817
- Jesko Hüttenhain and Pierre Lairez, The boundary of the orbit of the 3-by-3 determinant polynomial, C. R. Math. Acad. Sci. Paris 354 (2016), no. 9, 931–935 (English, with English and French summaries). MR 3535348, DOI 10.1016/j.crma.2016.07.002
- C. Ikenmeyer, Geometric Complexity Theory, Tensor Rank, and Littlewood–Richardson Coefficients, PhD thesis, Institute of Mathematics, University of Paderborn, 2012.
- Jesko Hüttenhain and Christian Ikenmeyer, Binary determinantal complexity, Linear Algebra Appl. 504 (2016), 559–573. MR 3502551, DOI 10.1016/j.laa.2016.04.027
- Christian Ikenmeyer, Ketan D. Mulmuley, and Michael Walter, On vanishing of Kronecker coefficients, Comput. Complexity 26 (2017), no. 4, 949–992. MR 3723353, DOI 10.1007/s00037-017-0158-y
- Christian Ikenmeyer and Greta Panova, Rectangular Kronecker coefficients and plethysms in geometric complexity theory, Adv. Math. 319 (2017), 40–66. MR 3695867, DOI 10.1016/j.aim.2017.08.024
- Harlan Kadish and J. M. Landsberg, Padded polynomials, their cousins, and geometric complexity theory, Comm. Algebra 42 (2014), no. 5, 2171–2180. MR 3169697, DOI 10.1080/00927872.2012.758268
- Shrawan Kumar, A study of the representations supported by the orbit closure of the determinant, Compos. Math. 151 (2015), no. 2, 292–312. MR 3314828, DOI 10.1112/S0010437X14007660
- Joseph M. Landsberg, Laurent Manivel, and Nicolas Ressayre, Hypersurfaces with degenerate duals and the geometric complexity theory program, Comment. Math. Helv. 88 (2013), no. 2, 469–484. MR 3048194, DOI 10.4171/CMH/292
- J. M. Landsberg and Zach Teitler, On the ranks and border ranks of symmetric tensors, Found. Comput. Math. 10 (2010), no. 3, 339–366. MR 2628829, DOI 10.1007/s10208-009-9055-3
- M. Larsen and R. Pink, Determining representations from invariant dimensions, Invent. Math. 102 (1990), no. 2, 377–398. MR 1074479, DOI 10.1007/BF01233432
- I. G. Macdonald, Symmetric functions and Hall polynomials, 2nd ed., Oxford Mathematical Monographs, The Clarendon Press, Oxford University Press, New York, 1995. With contributions by A. Zelevinsky; Oxford Science Publications. MR 1354144
- Guillaume Malod and Natacha Portier, Characterizing Valiant’s algebraic complexity classes, J. Complexity 24 (2008), no. 1, 16–38. MR 2386928, DOI 10.1016/j.jco.2006.09.006
- L. Manivel, Gaussian maps and plethysm, Algebraic geometry (Catania, 1993/Barcelona, 1994) Lecture Notes in Pure and Appl. Math., vol. 200, Dekker, New York, 1998, pp. 91–117. MR 1651092
- Thierry Mignon and Nicolas Ressayre, A quadratic bound for the determinant and permanent problem, Int. Math. Res. Not. 79 (2004), 4241–4253. MR 2126826, DOI 10.1155/S1073792804142566
- Ketan D. Mulmuley, On P vs. NP and geometric complexity theory, J. ACM 58 (2011), no. 2, Art. 5, 26. MR 2786586, DOI 10.1145/1944345.1944346
- Ketan D. Mulmuley and Milind Sohoni, Geometric complexity theory. I. An approach to the P vs. NP and related problems, SIAM J. Comput. 31 (2001), no. 2, 496–526. MR 1861288, DOI 10.1137/S009753970038715X
- Ketan D. Mulmuley and Milind Sohoni, Geometric complexity theory. II. Towards explicit obstructions for embeddings among class varieties, SIAM J. Comput. 38 (2008), no. 3, 1175–1206. MR 2421083, DOI 10.1137/080718115
- David Mumford, Algebraic geometry. I, Classics in Mathematics, Springer-Verlag, Berlin, 1995. Complex projective varieties; Reprint of the 1976 edition. MR 1344216
- F. D. Murnaghan, The Analysis of the Kronecker Product of Irreducible Representations of the Symmetric Group, Amer. J. Math. 60 (1938), no. 3, 761–784. MR 1507347, DOI 10.2307/2371610
- D. G. Northcott, Multilinear algebra, Cambridge University Press, Cambridge, 1984. MR 773853, DOI 10.1017/CBO9780511565939
- Richard P. Stanley, Positivity problems and conjectures in algebraic combinatorics, Mathematics: frontiers and perspectives, Amer. Math. Soc., Providence, RI, 2000, pp. 295–319. MR 1754784
- S. Toda, Classes of arithmetic circuits capturing the complexity of the determinant, IEICE Trans. Info. and Sys., E75-D (1992), no. 1, 116–124.
- 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
- L. G. Valiant, The complexity of computing the permanent, Theoret. Comput. Sci. 8 (1979), no. 2, 189–201. MR 526203, DOI 10.1016/0304-3975(79)90044-6
- L. G. Valiant, Reducibility by algebraic projections, Logic and algorithmic (Zurich, 1980) Monograph. Enseign. Math., vol. 30, Univ. Genève, Geneva, 1982, pp. 365–380. MR 648313
- Steven H. Weintraub, Some observations on plethysms, J. Algebra 129 (1990), no. 1, 103–114. MR 1037395, DOI 10.1016/0021-8693(90)90241-F
- A. Yabe, Bi-polynomial rank and determinantal complexity, arXiv:1504.00151 (2015).
Bibliographic Information
- Peter Bürgisser
- Affiliation: Technische Universität Berlin, Berlin, Germany
- MR Author ID: 316251
- Email: pbuerg@math.tu-berlin.de
- Christian Ikenmeyer
- Affiliation: Max Planck Institute for Informatics, Saarland Informatics Campus, Saarbrücken, Germany
- MR Author ID: 911976
- Email: cikenmey@mpi-inf.mpg.de
- Greta Panova
- Affiliation: University of Pennsylvania, Philadelphia, Pennsylvania; and Institute for Advanced Study, Princeton, New Jersey
- MR Author ID: 964307
- Email: panova@math.upenn.edu.
- Received by editor(s): March 9, 2017
- Received by editor(s) in revised form: April 20, 2018
- Published electronically: October 4, 2018
- Additional Notes: The first author was partially supported by DFG grant BU 1371/3-2.
The third author was partially supported by NSF grant DMS-1500834 - © Copyright 2018 American Mathematical Society
- Journal: J. Amer. Math. Soc. 32 (2019), 163-193
- MSC (2010): Primary 68Q17, 05E10, 14L24
- DOI: https://doi.org/10.1090/jams/908
- MathSciNet review: 3868002