Document Open Access Logo

On the Complexity of Evaluating Highest Weight Vectors

Authors Markus Bläser, Julian Dörfler , Christian Ikenmeyer

PDF
Thumbnail PDF

File

LIPIcs.CCC.2021.29.pdf
  • Filesize: 1.05 MB
  • 36 pages

Document Identifiers

Author Details

Markus Bläser
  • Saarland University, Saarland Informatics Campus, Saarbrücken, Germany
Julian Dörfler
  • Saarbrücken Graduate School of Computer Science, Saarland Informatics Campus, Germany
Christian Ikenmeyer
  • University of Liverpool, UK

Funding

  • Ikenmeyer, Christian: DFG grant IK 116/2-1.

Cite AsGet BibTex

Markus Bläser, Julian Dörfler, and Christian Ikenmeyer. On the Complexity of Evaluating Highest Weight Vectors. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 29:1-29:36, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.CCC.2021.29

Abstract

Geometric complexity theory (GCT) is an approach towards separating algebraic complexity classes through algebraic geometry and representation theory. Originally Mulmuley and Sohoni proposed (SIAM J Comput 2001, 2008) to use occurrence obstructions to prove Valiant’s determinant vs permanent conjecture, but recently Bürgisser, Ikenmeyer, and Panova (Journal of the AMS 2019) proved this impossible. However, fundamental theorems of algebraic geometry and representation theory grant that every lower bound in GCT can be proved by the use of so-called highest weight vectors (HWVs). In the setting of interest in GCT (namely in the setting of polynomials) we prove the NP-hardness of the evaluation of HWVs in general, and we give efficient algorithms if the treewidth of the corresponding Young-tableau is small, where the point of evaluation is concisely encoded as a noncommutative algebraic branching program! In particular, this gives a large new class of separating functions that can be efficiently evaluated at points with low (border) Waring rank. As a structural side result we prove that border Waring rank is bounded from above by the ABP width complexity.

Subject Classification

ACM Subject Classification
  • Theory of computation → Algebraic complexity theory
  • Mathematics of computing → Mathematical software
Keywords
  • Algebraic complexity theory
  • geometric complexity theory
  • algebraic branching program
  • Waring rank
  • border Waring rank
  • representation theory
  • highest weight vector
  • treewidth

Metrics

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

Related Versions

References

  1. Abdelmalek Abdesselam. Feynman diagrams in algebraic combinatorics. Séminaire Lotharingien de Combinatoire [electronic only], 49:B49c, 45 p., electronic only-B49c, 45 p., electronic only, 2002. URL: http://eudml.org/doc/123420.
  2. Abdelmalek Abdesselam, Christian Ikenmeyer, and Gordon Royle. 16,051 formulas for Ottaviani’s invariant of cubic threefolds. Journal of Algebra, 447:649-663, 2016. Google Scholar
  3. Daniel J. Bates and Luke Oeding. Toward a Salmon conjecture. Experimental Mathematics, 20(3):358-370, 2011. URL: https://doi.org/10.1080/10586458.2011.576539.
  4. Christine Bessenrodt and Christiane Behns. On the Durfee size of Kronecker products of characters of the symmetric group and its double covers. Journal of Algebra, 280(1):132-144, 2004. Google Scholar
  5. Christine Bessenrodt, Chris Bowman, and Rowena Paget. The classification of multiplicity-free plethysms of Schur functions, 2020. URL: http://arxiv.org/abs/2001.08763.
  6. D. Bini. Relations between exact and approximate bilinear algorithms. applications. CALCOLO, 17(1):87-97, January 1980. URL: https://doi.org/10.1007/BF02575865.
  7. Dario Bini, Milvio Capovani, Francesco Romani, and Grazia Lotti. O(n^2.7799) complexity for n × n approximate matrix multiplication. Inf. Process. Lett., 8(5):234-235, 1979. URL: https://doi.org/10.1016/0020-0190(79)90113-3.
  8. Markus Bläser and Christian Ikenmeyer. Introduction to geometric complexity theory, 2018. lecture notes, summer 2017 at Saarland University, http://people.mpi-inf.mpg.de/~cikenmey/teaching/summer17/introtogct/gct.pdf, version from July 25, 2018.
  9. Karl Bringmann, Christian Ikenmeyer, and Jeroen Zuiddam. On algebraic branching programs of small width. J. ACM, 65(5), 2018. URL: https://doi.org/10.1145/3209663.
  10. Russ Bubley, Martin E. Dyer, Catherine S. Greenhill, and Mark Jerrum. On approximately counting colorings of small degree graphs. SIAM J. Comput., 29(2):387-400, 1999. URL: https://doi.org/10.1137/S0097539798338175.
  11. Peter Bürgisser. The complexity of factors of multivariate polynomials. In 42nd IEEE Symposium on Foundations of Computer Science (Las Vegas, NV, 2001), pages 378-385. IEEE Computer Soc., Los Alamitos, CA, 2001. Google Scholar
  12. Peter Bürgisser, Matthias Christandl, and Christian Ikenmeyer. Even partitions in plethysms. Journal of Algebra, 328(1):322-329, 2011. Google Scholar
  13. 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
  14. 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
  15. Peter Bürgisser and Christian Ikenmeyer. Fundamental invariants of orbit closures. Journal of Algebra, 477(Supplement C):390-434, 2017. Google Scholar
  16. Peter Bürgisser, Christian Ikenmeyer, and Greta Panova. No occurrence obstructions in geometric complexity theory. Journal of the American Mathematical Society, 32:163-193, 2019. A conference version appeared in: Proceedings IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS 2016), 386-395. Google Scholar
  17. Peter Bürgisser, J.M. Landsberg, Laurent Manivel, and Jerzy Weyman. An overview of mathematical issues arising in the Geometric complexity theory approach to VP v.s. VNP. SIAM J. Comput., 40(4):1179-1209, 2011. Google Scholar
  18. Liming Cai and David Juedes. Subexponential parameterized algorithms collapse the w-hierarchy. In International Colloquium on Automata, Languages, and Programming, pages 273-284. Springer, 2001. Google Scholar
  19. Enrico Carlini, Maria Virginia Catalisano, and Anthony V Geramita. The solution to the Waring problem for monomials and the sum of coprime monomials. Journal of algebra, 370:5-14, 2012. Google Scholar
  20. Man-Wai Cheung, Christian Ikenmeyer, and Sevak Mkrtchyan. Symmetrizing tableaux and the 5th case of the Foulkes conjecture. Journal of Symbolic Computation, 80:833-843, 2017. Google Scholar
  21. Luca Chiantini, Jonathan D. Hauenstein, Christian Ikenmeyer, Joseph M. Landsberg, and Giorgio Ottaviani. Polynomials and the exponent of matrix multiplication. Bulletin of the London Mathematical Society, 50(3):369-389, 2018. URL: https://doi.org/10.1112/blms.12147.
  22. Matthias Christandl, Brent Doran, and Michael Walter. Computing multiplicities of lie group representations. In Proceedings of the 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, FOCS ’12, page 639–648, USA, 2012. IEEE Computer Society. URL: https://doi.org/10.1109/FOCS.2012.43.
  23. Marek Cygan, Fedor V Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Parameterized algorithms, volume 4(8). Springer, 2015. Google Scholar
  24. Noah Daleo, Jonathan Hauenstein, and Luke Oeding. Computations and equations for Segre-Grassmann hypersurfaces. Portugaliae Mathematica, 73, August 2014. URL: https://doi.org/10.4171/PM/1977.
  25. 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, July 9-12, 2019, Patras, Greece., pages 51:1-51:14, 2019. journal version accepted for publication in SIAM J Appl Alg Geom (SIAGA). URL: https://doi.org/10.4230/LIPIcs.ICALP.2019.51.
  26. Cameron Farnsworth. Koszul–young flattenings and symmetric border rank of the determinant. Journal of Algebra, 447:664-676, 2016. URL: https://doi.org/10.1016/j.jalgebra.2015.11.011.
  27. Nick Fischer and Christian Ikenmeyer. The computational complexity of plethysm coefficients. computational complexity, 29(2):8, November 2020. URL: https://doi.org/10.1007/s00037-020-00198-4.
  28. Michael Forbes. Some concrete questions on the border complexity of polynomials. Talk presented at the Workshop on Algebraic Complexity Theory, WACT 2016, Tel Aviv, 2016. video available at https://www.cs.tau.ac.il/~shpilka/wact2016/videos/index.php accessed 10/17/2019.
  29. Michael Andrew Forbes. Polynomial Identity Testing of Read-Once Oblivious Algebraic Branching Programs. PhD thesis, MIT, 2014. URL: https://dspace.mit.edu/handle/1721.1/89843.
  30. M. R. Garey, David S. Johnson, and Larry J. Stockmeyer. Some simplified np-complete graph problems. Theor. Comput. Sci., 1(3):237-267, 1976. URL: https://doi.org/10.1016/0304-3975(76)90059-1.
  31. Joshua A. Grochow, Ketan D. Mulmuley, and Youming Qiao. Boundaries of VP and VNP. In Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi, editors, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), volume 55 of Leibniz International Proceedings in Informatics (LIPIcs), pages 34:1-34:14, Dagstuhl, Germany, 2016. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.ICALP.2016.34.
  32. Charles Hermite. Sur la theorie des fonctions homogenes à deux indéterminées. Cambridge and Dublin Mathematical Journal, 9:172-217, 1854. Google Scholar
  33. Anthony Iarrobino and Vassil Kanev. Power sums, Gorenstein algebras, and determinantal loci. Springer Science & Business Media, 1999. Google Scholar
  34. 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.
  35. Christian Ikenmeyer. The Saxl conjecture and the dominance order. Discrete Mathematics, 338(11):1970-1975, 2015. Google Scholar
  36. Christian Ikenmeyer and Umangathan Kandasamy. Implementing geometric complexity theory: On the separation of orbit closures via symmetries. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, page 713–726, New York, NY, USA, 2020. Association for Computing Machinery. URL: https://doi.org/10.1145/3357713.3384257.
  37. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? J. Comput. Syst. Sci., 63(4):512-530, 2001. URL: https://doi.org/10.1006/jcss.2001.1774.
  38. Mrinal Kumar. On top fan-in vs formal degree for depth-3 arithmetic circuits, 2018. URL: https://eccc.weizmann.ac.il/report/2018/068/revision/1/download.
  39. Shrawan Kumar. A study of the representations supported by the orbit closure of the determinant. Compositio Mathematica, 151, September 2011. URL: https://doi.org/10.1112/S0010437X14007660.
  40. Shrawan Kumar and J.M. Landsberg. Connections between conjectures of Alon-Tarsi, Hadamard-Howe, and integrals over the special unitary group. Discrete Math., 338(7):1232-1238, 2015. URL: https://doi.org/10.1016/j.disc.2015.01.027.
  41. J. M. Landsberg. Geometric complexity theory: an introduction for geometers. Annali dell'Università di Ferrara, 61(1):65-117, 2015. URL: https://doi.org/10.1007/s11565-014-0202-7.
  42. Joseph Landsberg. Tensors: Geometry and Applications, volume 128 of Graduate Studies in Mathematics. American Mathematical Society, Providence, Rhode Island, 2011. Google Scholar
  43. M.A.A. Leeuwen, van, A.M. Cohen, and B. Lisser. Lie : a package for Lie group computations. Centrum voor Wiskunde en Informatica, 1992. Google Scholar
  44. Laurent Manivel and Mateusz Michałek. Effective constructions in plethysms and Weintraub’s conjecture. Algebras and Representation Theory, 17(2):433-443, April 2014. URL: https://doi.org/10.1007/s10468-012-9402-y.
  45. 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
  46. 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
  47. Noam Nisan. Lower bounds for non-commutative computation. In Proceedings of the 23rd ACM Symposium on Theory of Computing, ACM Press. Citeseer, 1991. Google Scholar
  48. Luke Oeding and Claudiu Raicu. Tangential varieties of Segre-Veronese varieties. Collectanea Mathematica, 65, November 2011. URL: https://doi.org/10.1007/s13348-014-0111-1.
  49. Giorgio Ottaviani. Five lectures on projective invariants, lecture notes for trento school, september 2012, 2013. https://arxiv.org/abs/1305.2749, to appear in Rendiconti del Seminario Matematico, Torino.
  50. Claudiu Raicu. 3× 3 minors of catalecticants. Mathematical Research Letters, 20, July 2013. URL: https://doi.org/10.4310/MRL.2013.v20.n4.a10.
  51. Neil Robertson, Paul D. Seymour, and Robin Thomas. Quickly excluding a planar graph. J. Comb. Theory, Ser. B, 62(2):323-348, 1994. URL: https://doi.org/10.1006/jctb.1994.1073.
  52. Steven Sam and Andrew Snowden. Proof of stembridge’s conjecture on stability of Kronecker coefficients. Journal of Algebraic Combinatorics, 43:1-10, 2016. Google Scholar
  53. Nitin Saxena. Diagonal circuit identity testing and lower bounds. In Automata, Languages and Programming, pages 60-71, Berlin, Heidelberg, 2008. Springer Berlin Heidelberg. Google Scholar
  54. Yaroslav Shitov. How hard is the tensor rank?, 2016. URL: http://arxiv.org/abs/1611.01559.
  55. Roberto Tamassia and Ioannis G Tollis. Planar grid embedding in linear time. IEEE Transactions on circuits and systems, 36(9):1230-1234, 1989. 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-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact