No occurrence obstructions in geometric complexity theory

Bürgisser, Peter; Ikenmeyer, Christian; Panova, Greta

doi:10.1090/jams/908

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