Document Open Access Logo

On Geometric Complexity Theory: Multiplicity Obstructions Are Stronger Than Occurrence Obstructions

Authors Julian Dörfler, Christian Ikenmeyer, Greta Panova

PDF

File

Thumbnail PDF
PDF
LIPIcs.ICALP.2019.51.pdf
  • Filesize: 0.51 MB
  • 14 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Algebraic complexity theory
Keywords
  • Algebraic complexity theory
  • geometric complexity theory
  • Waring rank
  • plethysm coefficients
  • occurrence obstructions
  • multiplicity obstructions

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

Geometric Complexity Theory as initiated by Mulmuley and Sohoni in two papers (SIAM J Comput 2001, 2008) aims to separate algebraic complexity classes via representation theoretic multiplicities in coordinate rings of specific group varieties. We provide the first toy setting in which a separation can be achieved for a family of polynomials via these multiplicities.
Mulmuley and Sohoni’s papers also conjecture that the vanishing behavior of multiplicities would be sufficient to separate complexity classes (so-called occurrence obstructions). The existence of such strong occurrence obstructions has been recently disproven in 2016 in two successive papers, Ikenmeyer-Panova (Adv. Math.) and Bürgisser-Ikenmeyer-Panova (J. AMS). This raises the question whether separating group varieties via representation theoretic multiplicities is stronger than separating them via occurrences. We provide first finite settings where a separation via multiplicities can be achieved, while the separation via occurrences is provably impossible. These settings are surprisingly simple and natural: We study the variety of products of homogeneous linear forms (the so-called Chow variety) and the variety of polynomials of bounded border Waring rank (i.e. a higher secant variety of the Veronese variety).
As a side result we prove a slight generalization of Hermite’s reciprocity theorem, which proves Foulkes' conjecture for a new infinite family of cases.

Cite As Get BibTex

Julian Dörfler, Christian Ikenmeyer, and Greta Panova. On Geometric Complexity Theory: Multiplicity Obstructions Are Stronger Than Occurrence Obstructions. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 51:1-51:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.ICALP.2019.51

Author Details

Julian Dörfler
  • Saarland University, Saarbrücken, Germany
Christian Ikenmeyer
  • Max Planck Institute for Software Systems, Saarbrücken, Germany
Greta Panova
  • University of Southern Californa, Los Angeles, CA, USA
  • University of Pennsylvania, Philadelphia, PA, USA

Funding

  • Dörfler, Julian: Partially supported by DFG grant IK 116/2-1.
  • Ikenmeyer, Christian: Partially supported by DFG grant IK 116/2-1.
  • Panova, Greta: Partially funded by the NSF.

Acknowledgements

This work was done in part while CI and GP were visiting the Simons Institute for the Theory of Computing.

References

  1. Markus Bläser and Christian Ikenmeyer. Introduction to geometric complexity theory. lecture notes, summer 2017 at Saarland University, version July 25, 2018, http://people.mpi-inf.mpg.de/~cikenmey/teaching/summer17/introtogct/gct.pdf, 2018.
  2. Emmanuel Briand, Rosa Orellana, and Mercedes Rosas. Reduced Kronecker coefficients and counter-examples to Mulmuley’s strong saturation conjecture SH. Computational Complexity, 18:577-600, 2009. Google Scholar
  3. Peter Bürgisser, Michael Clausen, and M. Amin Shokrollahi. Algebraic complexity theory, volume 315 of Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. Springer-Verlag, Berlin, 1997. With the collaboration of Thomas Lickteig. Google Scholar
  4. Peter Bürgisser, Jesko Hüttenhain, and Christian Ikenmeyer. Permanent versus determinant: not via saturations. Proceedings of the American Mathematical Society, 145(3):1247-1258, 2017. Google Scholar
  5. Peter Bürgisser and Christian Ikenmeyer. The complexity of computing Kronecker coefficients. In FPSAC 2008, Valparaiso-Viña del Mar, Chile, DMTCS proc. AJ, pages 357-368, 2008. Google Scholar
  6. Peter Bürgisser and Christian Ikenmeyer. Geometric Complexity Theory and Tensor Rank. Proceedings 43rd Annual ACM Symposium on Theory of Computing 2011, pages 509-518, 2011. Google Scholar
  7. Peter Bürgisser and Christian Ikenmeyer. Explicit Lower Bounds via Geometric Complexity Theory. Proceedings 45th Annual ACM Symposium on Theory of Computing 2013, pages 141-150, 2013. Google Scholar
  8. Peter Bürgisser, Christian Ikenmeyer, and Greta Panova. No occurrence obstructions in geometric complexity theory. Journal of the AMS, 32:163-193, 2019. An earlier version was presented at the IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS) 2016 in New Brunswick, New Jersey. Google Scholar
  9. Man-Wai Cheung, Christian Ikenmeyer, and Sevak Mkrtchyan. Symmetrizing tableaux and the 5th case of the Foulkes conjecture. Journal of Symbolic Computation, 80(3):833-843, 2016. URL: http://dx.doi.org/10.1016/j.jsc.2016.09.002.
  10. W. Fulton. Young tableaux, volume 35 of London Mathematical Society Student Texts. Cambridge University Press, Cambridge, 1997. Google Scholar
  11. Roe Goodman and Nolan R. Wallach. Symmetry, representations, and invariants, volume 255 of Graduate Texts in Mathematics. Springer, Dordrecht, 2009. Google Scholar
  12. Yonghui Guan. Brill’s equations as a GL(V)-module. Linear Algebra and its Applications, 548:273-292, 2018. URL: http://dx.doi.org/10.1016/j.laa.2018.02.026.
  13. Charles Hermite. Sur la théorie des fonctions homogenes à deux indéterminées. Cambridge and Dublin Mathematical Journal, 9:172-217, 1854. Google Scholar
  14. Christian Ikenmeyer. Geometric Complexity Theory, Tensor Rank, and Littlewood-Richardson Coefficients. PhD thesis, Institute of Mathematics, University of Paderborn, 2012. URL: http://nbn-resolving.de/urn:nbn:de:hbz:466:2-10472.
  15. Christian Ikenmeyer. GCT and symmetries. unpublished lecture notes, version from January 29, 2018. Google Scholar
  16. Christian Ikenmeyer and Greta Panova. Rectangular Kronecker Coefficients and Plethysms in Geometric Complexity Theory. Advances in Mathematics, 319:40-66, 2017. An earlier version was presented at the IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS) 2016 in New Brunswick, New Jersey. Google Scholar
  17. Harlan Kadish and J. M. Landsberg. Padded Polynomials, Their Cousins, and Geometric Complexity Theory. Communications in Algebra, 42(5):2171-2180, 2014. URL: http://dx.doi.org/10.1080/00927872.2012.758268.
  18. Hanspeter Kraft. Geometrische Methoden in der Invariantentheorie. Friedr. Vieweg und Sohn Verlagsgesellschaft, Braunschweig, 1985. Google Scholar
  19. J. M. Landsberg. Geometry and Complexity Theory. Cambridge Studies in Advanced Mathematics. Cambridge University Press, 2017. URL: http://dx.doi.org/10.1017/9781108183192.
  20. Joseph Landsberg. Tensors: Geometry and Applications, volume 128 of Graduate Studies in Mathematics. American Mathematical Society, Providence, Rhode Island, 2011. Google Scholar
  21. I. G. Macdonald. Symmetric functions and Hall polynomials. Oxford Mathematical Monographs. The Clarendon Press, Oxford University Press, New York, second edition, 1995. With contributions by A. Zelevinsky, Oxford Science Publications. Google Scholar
  22. K.D. Mulmuley and M. Sohoni. Geometric Complexity Theory. I. An approach to the P vs. NP and related problems. SIAM J. Comput., 31(2):496-526 (electronic), 2001. Google Scholar
  23. K.D. Mulmuley and M. Sohoni. Geometric Complexity Theory. II. Towards explicit obstructions for embeddings among class varieties. SIAM J. Comput., 38(3):1175-1206, 2008. Google Scholar
  24. D. Mumford. Algebraic geometry. I: Complex projective varieties. Classics in mathematics. Springer-Verlag, Berlin, 1995. Reprint of the 1976 edition in Grundlehren der mathematischen Wissenschaften, vol. 221. Google Scholar
  25. Hariharan Narayanan. On the complexity of computing Kostka numbers and Littlewood-Richardson coefficients. J. Algebraic Combin., 24(3):347-354, 2006. Google Scholar
  26. Igor Pak and Greta Panova. Strict unimodality of q-binomial coefficients. C. R. Math. Acad. Sci. Paris, 351(11-12):415-418, 2013. URL: http://dx.doi.org/10.1016/j.crma.2013.06.008.
  27. Claudio Procesi. Lie groups. Universitext. Springer, New York, 2007. An approach through invariants and representations. Google Scholar
  28. Ramprasad Saptharishi. A survey of lower bounds in arithmetic circuit complexity. , version 3.1.4, 2017. URL: https://github.com/dasarpmar/lowerbounds-survey.
  29. Richard P. Stanley. Enumerative combinatorics. Vol. 2, volume 62 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 1999. With a foreword by Gian-Carlo Rota and appendix 1 by Sergey Fomin. Google Scholar
  30. Richard P. Stanley. Positivity problems and conjectures in algebraic combinatorics. In Mathematics: frontiers and perspectives, pages 295-319. Amer. Math. Soc., Providence, RI, 2000. Google Scholar
  31. Richard P. Stanley. Enumerative combinatorics. Vol. 1. Cambridge University Press, Cambridge, 2011. second edition. Google Scholar
  32. Bernd Sturmfels. Algorithms in Invariant Theory. Texts & Monographs in Symbolic Computation. Springer, 2008. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact