No occurrence obstructions in geometric complexity theory

Bürgisser, Peter¹ ; Ikenmeyer, Christian² ; Panova, Greta³

¹ Technische Universität Berlin, Berlin, Germany
² Max Planck Institute for Informatics, Saarland Informatics Campus, Saarbrücken, Germany
³ University of Pennsylvania, Philadelphia, Pennsylvania; and Institute for Advanced Study, Princeton, New Jersey

Journal of the American Mathematical Society, Tome 32 (2019) no. 1, pp. 163-193

Résumé

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.

Détail

DOI : 10.1090/jams/908

Bibliographie

[1] Alon, N., Tarsi, M. Colorings and orientations of graphs Combinatorica 1992 125 134

[2] Alper, Jarod, Bogart, Tristram, Velasco, Mauricio A lower bound for the determinantal complexity of a hypersurface Found. Comput. Math. 2017 829 836

[3] Bã¼Rgisser, Peter Completeness and reduction in algebraic complexity theory 2000

[4] Bã¼Rgisser, Peter Cook’s versus Valiant’s hypothesis Theoret. Comput. Sci. 2000 71 88

[5] Bã¼Rgisser, Peter The complexity of factors of multivariate polynomials Found. Comput. Math. 2004 369 396

[6] Bã¼Rgisser, Peter, Christandl, Matthias, Ikenmeyer, Christian Even partitions in plethysms J. Algebra 2011 322 329

[7] Bã¼Rgisser, Peter, Christandl, Matthias, Ikenmeyer, Christian Nonvanishing of Kronecker coefficients for rectangular shapes Adv. Math. 2011 2082 2091

[8] Bã¼Rgisser, Peter, Ikenmeyer, Christian, Hã¼Ttenhain, Jesko Permanent versus determinant: not via saturations Proc. Amer. Math. Soc. 2017 1247 1258

[9] Bã¼Rgisser, Peter, Ikenmeyer, Christian Fundamental invariants of orbit closures J. Algebra 2017 390 434

[10] Bã¼Rgisser, Peter, Ikenmeyer, Christian, Panova, Greta No occurrence obstructions in geometric complexity theory 2016 386 395

[11] Bã¼Rgisser, Peter, Landsberg, J. M., Manivel, Laurent, Weyman, Jerzy An overview of mathematical issues arising in the geometric complexity theory approach to 𝑉𝑃≠𝑉𝑁𝑃 SIAM J. Comput. 2011 1179 1209

[12] Cai, Jin-Yi, Chen, Xi, Li, Dong Quadratic lower bound for permanent vs. determinant in any characteristic Comput. Complexity 2010 37 56

[13] Carrã©, Christophe, Thibon, Jean-Yves Plethysm and vertex operators Adv. in Appl. Math. 1992 390 403

[14] Cayley, Arthur The collected mathematical papers. Volume 2 2009

[15] Christandl, Matthias, Doran, Brent, Walter, Michael Computing multiplicities of Lie group representations 2012 639 648

[16] Dolgachev, Igor Lectures on invariant theory 2003

[17] Fulton, William, Harris, Joe Representation theory 1991

[18] Gesmundo, Fulvio, Ikenmeyer, Christian, Panova, Greta Geometric complexity theory and matrix powering Differential Geom. Appl. 2017 106 127

[19] Howe, Roger (𝐺𝐿_{𝑛},𝐺𝐿ₘ)-duality and symmetric plethysm Proc. Indian Acad. Sci. Math. Sci. 1987

[20] Hã¼Ttenhain, Jesko, Lairez, Pierre The boundary of the orbit of the 3-by-3 determinant polynomial C. R. Math. Acad. Sci. Paris 2016 931 935

[21] Hã¼Ttenhain, Jesko, Ikenmeyer, Christian Binary determinantal complexity Linear Algebra Appl. 2016 559 573

[22] Ikenmeyer, Christian, Mulmuley, Ketan D., Walter, Michael On vanishing of Kronecker coefficients Comput. Complexity 2017 949 992

[23] Ikenmeyer, Christian, Panova, Greta Rectangular Kronecker coefficients and plethysms in geometric complexity theory Adv. Math. 2017 40 66

[24] Kadish, Harlan, Landsberg, J. M. Padded polynomials, their cousins, and geometric complexity theory Comm. Algebra 2014 2171 2180

[25] Kumar, Shrawan A study of the representations supported by the orbit closure of the determinant Compos. Math. 2015 292 312

[26] Landsberg, Joseph M., Manivel, Laurent, Ressayre, Nicolas Hypersurfaces with degenerate duals and the geometric complexity theory program Comment. Math. Helv. 2013 469 484

[27] Landsberg, J. M., Teitler, Zach On the ranks and border ranks of symmetric tensors Found. Comput. Math. 2010 339 366

[28] Larsen, M., Pink, R. Determining representations from invariant dimensions Invent. Math. 1990 377 398

[29] Macdonald, I. G. Symmetric functions and Hall polynomials 1995

[30] Malod, Guillaume, Portier, Natacha Characterizing Valiant’s algebraic complexity classes J. Complexity 2008 16 38

[31] Manivel, L. Gaussian maps and plethysm 1998 91 117

[32] Mignon, Thierry, Ressayre, Nicolas A quadratic bound for the determinant and permanent problem Int. Math. Res. Not. 2004 4241 4253

[33] Mulmuley, Ketan D. On P vs. NP and geometric complexity theory J. ACM 2011

[34] Mulmuley, Ketan D., Sohoni, Milind Geometric complexity theory. I. An approach to the P vs. NP and related problems SIAM J. Comput. 2001 496 526

[35] Mulmuley, Ketan D., Sohoni, Milind Geometric complexity theory. II. Towards explicit obstructions for embeddings among class varieties SIAM J. Comput. 2008 1175 1206

[36] Mumford, David Algebraic geometry. I 1995

[37] Murnaghan, F. D. The Analysis of the Kronecker Product of Irreducible Representations of the Symmetric Group Amer. J. Math. 1938 761 784

[38] Northcott, D. G. Multilinear algebra 1984

[39] Stanley, Richard P. Positivity problems and conjectures in algebraic combinatorics 2000 295 319

[40] Valiant, L. G. Completeness classes in algebra 1979 249 261

[41] Valiant, L. G. The complexity of computing the permanent Theoret. Comput. Sci. 1979 189 201

[42] Valiant, L. G. Reducibility by algebraic projections 1982 365 380

[43] Weintraub, Steven H. Some observations on plethysms J. Algebra 1990 103 114