research-article

Free access

Geometric complexity theory and tensor rank

Authors:

Peter Bürgisser,

Christian IkenmeyerAuthors Info & Claims

STOC '11: Proceedings of the forty-third annual ACM symposium on Theory of computing

Pages 509 - 518

https://doi.org/10.1145/1993636.1993704

Published: 06 June 2011 Publication History

Abstract

Mulmuley and Sohoni [GCT1, SICOMP 2001; GCT2, SICOMP 2008] proposed to view the permanent versus determinant problem as a specific orbit closure problem and to attack it by methods from geometric invariant and representation theory. We adopt these ideas towards the goal of showing lower bounds on the border rank of specific tensors, in particular for matrix multiplication. We thus study specific orbit closure problems for the group G =GL(W₁) x GL(W₂) x GL(W₃) acting on the tensor product W=W₁ ⊗ W₂ ⊗ W₃ of complex finite dimensional vector spaces. Let G_s =SL(W₁) x SL(W₂) x SL(W₃). A key idea from [GCT2] is that the irreducible G_s-representations occurring in the coordinate ring of the G-orbit closure of a stable tensor w ∈ W are exactly those having a nonzero invariant with respect to the stabilizer group of w.

However, we prove that by considering G_s-representations, only trivial lower bounds on border rank can be shown. It is thus necessary to study G-representations, which leads to geometric extension problems that are beyond the scope of the subgroup restriction problems emphasized in [GCT1, GCT2] and its follow up papers. We prove a very modest lower bound on the border rank of matrix multiplication tensors using G-representations. This shows at least that the barrier for G_s-representations can be overcome. To advance, we suggest the coarser approach to replace the semigroup of representations of a tensor by its moment polytope. We prove first results towards determining the moment polytopes of matrix multiplication and unit tensors.

Supplementary Material

JPG File (stoc_8b_3.jpg)

Download
18.61 KB

MP4 File (stoc_8b_3.mp4)

Download
87.15 MB

References

[1]

Arkady Berenstein and Reyer Sjamaar, phCoadjoint orbits, moment polytopes, and the Hilbert-Mumford criterion, J. Amer. Math. Soc. 13 (2000), no. 2, 433--466 (electronic).

[2]

Markus Bläser, A 5/2 n<sup>2</sup>-lower bound for the rank of n x n-matrix multiplication over arbitrary fields, 40th Annual Symposium on Foundations of Computer Science (New York, 1999), IEEE Computer Soc., Los Alamitos, CA, 1999, pp. 45--50.

Digital Library

[3]

Michel Brion, Sur l'image de l'application moment, Séminaire d'algèbre Paul Dubreil et Marie-Paule Malliavin (Paris, 1986), Lecture Notes in Math., vol. 1296, Springer, Berlin, 1987, pp. 177--192.

[4]

Peter Bürgisser, Matthias Christandl, and Christian Ikenmeyer, Nonvanishing of Kronecker coefficients for rectangular shapes, arXiv 0910.4512v2 (2009).

[5]

Peter Bürgisser, Michael Clausen, and M. Amin Shokrollahi, Algebraic complexity theory, Grundlehren der Mathematischen Wissenschaften, vol. 315, Springer-Verlag, Berlin, 1997.

Digital Library

[6]

Peter Bürgisser, J.M. Landsberg, Laurent Manivel, and Jerzy Weyman, An overview of mathematial issues arising in the geometric complexity theory approach to VP≠VNP, arXiv:0907.2850v1 (2009).

[7]

Matthias Christandl and Graeme Mitchison, The spectra of density operators and the Kronecker coefficients of the symmetric group, Comm. Math. Phys. 261 (2006), no. 3, 789--797.

[8]

Michael Clausen and Helga Meier, Extreme irreduzible Konstituenten in Tensordarstellungen symmetrischer Gruppen, Bayreuth. Math. Schr. (1993), no. 45, 1--17.

[9]

Don Coppersmith and Shmuel Winograd, Matrix multiplication via arithmetic progressions, J. Symbolic Comput. 9 (1990), no. 3, 251--280.

Digital Library

[10]

Hans F. de Groote, On varieties of optimal algorithms for the computation of bilinear mappings. I. The isotropy group of a bilinear mapping, Theoret. Comput. Sci. 7 (1978), no. 1, 1--24.

[11]

William Fulton, Young tableaux, London Mathematical Society Student Texts, vol. 35, Cambridge University Press, Cambridge, 1997.

[12]

William Fulton and Joe Harris, Representation theory, Graduate Texts in Mathematics, vol. 129, Springer-Verlag, New York, 1991.

[13]

D.A. Gay, Characters of the Weyl group of SU(n) on zero weight spaces and centralizers of permutation representations, Rocky Mountain J. Math. 6 (1976), no. 3, 449--455.

[14]

Roe Goodman and Nolan R. Wallach, Symmetry, representations, and invariants, Graduate Texts in Mathematics, vol. 255, Springer, Dordrecht, 2009.

[15]

Robin Hartshorne, Algebraic geometry, Graduate Texts in Mathematics, no. 52, Springer, 1977.

[16]

Israel N. Herstein, Noncommutative rings, The Carus Math. Monographs, vol. 15, Math. Assoc. of America, 1994.

[17]

George R. Kempf, Instability in invariant theory, Ann. of Math. (2) 108 (1978), no. 2, 299--316.

[18]

Alexander Klyachko, Quantum marginal problem and representations of the symmetric group, arXiv:quant-ph/0409113, 2003.

[19]

Hanspeter Kraft, Geometrische Methoden in der Invariantentheorie, Aspects of Mathematics, D1, Friedr. Vieweg & Sohn, Braunschweig, 1984.

[20]

Shrawan Kumar, Geometry of orbits of permanents and determinants, Preprint, 2010.

[21]

Joseph M. Landsberg, The border rank of the multiplication of $2\times2$ matrices is seven, J. Amer. Math. Soc. 19 (2006), no. 2, 447--459.

[22]

Joseph M. Landsberg and L. Manivel, On the ideals of secant varieties of Segre varieties, Found. Comput. Math. 4 (2004), no. 4, 397--422.

Digital Library

[23]

Thomas Lickteig, A note on border rank, Inform. Process. Lett. 18 (1984), no. 3, 173--178.

[24]

Andreas Meyer, Geometric complexity theory and matrix multiplication, Ph.D. thesis, ETH Zürich, 2006, No. 16845.

[25]

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

Digital Library

[26]

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.

Digital Library

[27]

David Mumford, The red book of varieties and schemes, Lecture Notes in Math., no. 1358, Springer-Verlag, 1988.

[28]

Jeffrey B. Remmel and Tamsen Whitehead, On the Kronecker product of Schur functions of two row shapes, Bull. Belg. Math. Soc. Simon Stevin 1 (1994), no. 5, 649--683.

[29]

Nicolas Ressayre, Geometric invariant theory and generalized eigenvalue problem II, arXiv:0903.1187, 2009.

[30]

Mercedes H. Rosas, The Kronecker product of Schur functions indexed by two-row shapes or hook shapes, J. Algebraic Combin. 14 (2001), no. 2, 153--173.

Digital Library

[31]

Richard P. Stanley, Enumerative combinatorics. Vol. 2, Cambridge Studies in Advanced Mathematics, vol. 62, Cambridge University Press, Cambridge, 1999.

[32]

Volker Strassen, Vermeidung von Divisionen, J. Reine Angew. Math. 264 (1973), 184--202.

[33]

Volker Strassen, Vermeidung von Divisionen, J. Reine Angew. Rank and optimal computation of generic tensors, Linear Algebra Appl. 52/53 (1983), 645--685.

[34]

Volker Strassen, Vermeidung von Divisionen, J. Reine Angew. Relative bilinear complexity and matrix multiplication, J. Reine Angew. Math. 375/376 (1987), 406--443.

[35]

Volker Strassen, Vermeidung von Divisionen, J. Reine Angew. Komplexität und Geometrie bilinearer Abbildungen, Jahresber. Deutsch. Math.-Verein. 107 (2005), no. 1, 3--31.

Cited By

Gilchrist VMarco LPetit CTang G(2024)Solving the Tensor Isomorphism Problem for Special Orbits with Low Rank Points: Cryptanalysis and Repair of an Asiacrypt 2023 Commitment SchemeAdvances in Cryptology – CRYPTO 202410.1007/978-3-031-68376-3_5(141-173)Online publication date: 16-Aug-2024
https://doi.org/10.1007/978-3-031-68376-3_5
Wang KSeigal A(2023)Lower bounds on the rank and symmetric rank of real tensorsJournal of Symbolic Computation10.1016/j.jsc.2023.01.004118(69-92)Online publication date: Sep-2023
https://doi.org/10.1016/j.jsc.2023.01.004
Breiding PHodges RIkenmeyer CMichałek M(2022)Equations for GL Invariant Families of PolynomialsVietnam Journal of Mathematics10.1007/s10013-022-00549-450:2(545-556)Online publication date: 24-Feb-2022
https://doi.org/10.1007/s10013-022-00549-4
Show More Cited By

Index Terms

Geometric complexity theory and tensor rank
1. Mathematics of computing
  1. Mathematical analysis
    1. Numerical analysis
      1. Computations on polynomials
2. Theory of computation
  1. Computational complexity and cryptography
    1. Complexity classes

Recommendations

Explicit lower bounds via geometric complexity theory
STOC '13: Proceedings of the forty-fifth annual ACM symposium on Theory of Computing

We prove the lower bound R M_m) ≥ 3/2 m²-2 on the border rank of m x m matrix multiplication by exhibiting explicit representation theoretic (occurence) obstructions in the sense of Mulmuley and Sohoni's geometric complexity theory (GCT) program. While ...
Asymptotic tensor rank of graph tensors: beyond matrix multiplication

We present an upper bound on the exponent of the asymptotic behaviour of the tensor rank of a family of tensors defined by the complete graph on k vertices. For $${k \geq 4}$$k?4, we show that the exponent per edge is at most 0.77, outperforming the ...
Tensor surgery and tensor rank

We introduce a method for transforming low-order tensors into higher-order tensors and apply it to tensors defined by graphs and hypergraphs. The transformation proceeds according to a surgery-like procedure that splits vertices, creates and absorbs ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC '11: Proceedings of the forty-third annual ACM symposium on Theory of computing

June 2011

840 pages

ISBN:9781450306911

DOI:10.1145/1993636

General Chair:
Lance Fortnow
Northwestern University
,
Program Chair:
Salil Vadhan
Harvard University

Copyright © 2011 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 June 2011

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

STOC'11

Sponsor:

SIGACT

STOC'11: Symposium on Theory of Computing

June 6 - 8, 2011

California, San Jose, USA

Acceptance Rates

STOC '11 Paper Acceptance Rate 84 of 304 submissions, 28%;

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

23
Total Citations
View Citations
611
Total Downloads

Downloads (Last 12 months)127
Downloads (Last 6 weeks)15

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Gilchrist VMarco LPetit CTang G(2024)Solving the Tensor Isomorphism Problem for Special Orbits with Low Rank Points: Cryptanalysis and Repair of an Asiacrypt 2023 Commitment SchemeAdvances in Cryptology – CRYPTO 202410.1007/978-3-031-68376-3_5(141-173)Online publication date: 16-Aug-2024
https://doi.org/10.1007/978-3-031-68376-3_5
Wang KSeigal A(2023)Lower bounds on the rank and symmetric rank of real tensorsJournal of Symbolic Computation10.1016/j.jsc.2023.01.004118(69-92)Online publication date: Sep-2023
https://doi.org/10.1016/j.jsc.2023.01.004
Breiding PHodges RIkenmeyer CMichałek M(2022)Equations for GL Invariant Families of PolynomialsVietnam Journal of Mathematics10.1007/s10013-022-00549-450:2(545-556)Online publication date: 24-Feb-2022
https://doi.org/10.1007/s10013-022-00549-4
Bläser MDörfler JIkenmeyer C(2021)On the complexity of evaluating highest weight vectorsProceedings of the 36th Computational Complexity Conference10.4230/LIPIcs.CCC.2021.29Online publication date: 20-Jul-2021
https://dl.acm.org/doi/10.4230/LIPIcs.CCC.2021.29
Christandl MVrana PZuiddam J(2021)Universal points in the asymptotic spectrum of tensorsJournal of the American Mathematical Society10.1090/jams/99636:1(31-79)Online publication date: 23-Nov-2021
https://doi.org/10.1090/jams/996
Ikenmeyer CKandasamy UMakarychev KMakarychev YTulsiani MKamath GChuzhoy J(2020)Implementing geometric complexity theory: on the separation of orbit closures via symmetriesProceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing10.1145/3357713.3384257(713-726)Online publication date: 22-Jun-2020
https://dl.acm.org/doi/10.1145/3357713.3384257
Christandl MZuiddam J(2019)Tensor surgery and tensor rankComputational Complexity10.1007/s00037-018-0164-828:1(27-56)Online publication date: 1-Mar-2019
https://dl.acm.org/doi/10.1007/s00037-018-0164-8
Bringmann KIkenmeyer CZuiddam J(2018)On Algebraic Branching Programs of Small WidthJournal of the ACM10.1145/320966365:5(1-29)Online publication date: 29-Aug-2018
https://dl.acm.org/doi/10.1145/3209663
Christandl MVrana PZuiddam JDiakonikolas IKempe DHenzinger M(2018)Universal points in the asymptotic spectrum of tensorsProceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3188745.3188766(289-296)Online publication date: 20-Jun-2018
https://dl.acm.org/doi/10.1145/3188745.3188766
Burgisser PFranks CGarg AOliveira RWalter MWigderson A(2018)Efficient Algorithms for Tensor Scaling, Quantum Marginals, and Moment Polytopes2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS.2018.00088(883-897)Online publication date: Oct-2018
https://doi.org/10.1109/FOCS.2018.00088
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents