research-article

Geometric rank of tensors and subrank of matrix multiplication

Authors:

Swastik Kopparty,

Guy Moshkovitz,

Jeroen ZuiddamAuthors Info & Claims

CCC '20: Proceedings of the 35th Computational Complexity Conference

Article No.: 35, Pages 1 - 21

https://doi.org/10.4230/LIPIcs.CCC.2020.35

Published: 08 October 2020 Publication History

Abstract

Motivated by problems in algebraic complexity theory (e.g., matrix multiplication) and extremal combinatorics (e.g., the cap set problem and the sunflower problem), we introduce the geometric rank as a new tool in the study of tensors and hypergraphs. We prove that the geometric rank is an upper bound on the subrank of tensors and the independence number of hypergraphs. We prove that the geometric rank is smaller than the slice rank of Tao, and relate geometric rank to the analytic rank of Gowers and Wolf in an asymptotic fashion. As a first application, we use geometric rank to prove a tight upper bound on the (border) subrank of the matrix multiplication tensors, matching Strassen's well-known lower bound from 1987.

References

[1]

Josh Alman. Limits on the universal method for matrix multiplication. In Proceedings of the 34th Computational Complexity Conference (CCC 2019), pages 12:1--12:24, 2019.

[2]

Josh Alman and Virginia Vassilevska Williams. Limits on all known (and some unknown) approaches to matrix multiplication. In Proceedings of the 59th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2018), pages 580--591, 2018.

[3]

Andris Ambainis, Yuval Filmus, and Frangois Le Gall. Fast matrix multiplication: limitations of the Coppersmith-Winograd method (extended abstract). In Proceedings of the 47th Annual ACM Symposium on Theory of Computing (STOC 2015), pages 585--593, 2015.

Digital Library

[4]

Daniel Berend and Yuri Bilu. Polynomials with roots modulo every integer. Proc. Amer. Math. Soc., 124(6):1663--1671, 1996.

[5]

Abhishek Bhowmick and Shachar Lovett. Bias vs structure of polynomials in large fields, and applications in effective algebraic geometry and coding theory. arXiv, 2015. arXiv:1506.02047.

[6]

Abhishek Bhrushundi, Prahladh Harsha, Pooya Hatami, Swastik Kopparty, and Mrinal Kumar. On multilinear forms: Bias, correlation, and tensor rank. arXiv, 2018. arXiv:1804.09124.

[7]

Jonah Blasiak, Thomas Church, Henry Cohn, Joshua A. Grochow, Eric Naslund, William F. Sawin, and Chris Umans. On cap sets and the group-theoretic approach to matrix multiplication. Discrete Anal., 2017.

[8]

Jonah Blasiak, Thomas Church, Henry Cohn, Joshua A Grochow, and Chris Umans. Which groups are amenable to proving exponent two for matrix multiplication? arXiv, 2017. arXiv:1712.02302.

[9]

Markus Bläser, Christian Ikenmeyer, Vladimir Lysikov, Anurag Pandey, and Frank-Olaf Schreyer. Variety membership testing, algebraic natural proofs, and geometric complexity theory. arXiv, 2019. arXiv:1911.02534.

[10]

Jop Briët. Subspaces of tensors with high analytic rank. arXiv, 2019. arXiv:1908.04169.

[11]

Peter Bürgisser, Michael Clausen, and M. Amin Shokrollahi. Algebraic complexity theory, volume 315 of Grundlehren Math. Wiss. Springer-Verlag, Berlin, 1997.

[12]

Matthias Christandl, Angelo Lucia, Péter Vrana, and Albert H. Werner. Tensor network representations from the geometry of entangled states. arXiv, 2018. arXiv:1809.08185.

[13]

Matthias Christandl, Péter Vrana, and Jeroen Zuiddam. Universal points in the asymptotic spectrum of tensors (extended abstract). In Proceedings of 50th Annual ACM SIGACT Symposium on the Theory of Computing (STOC'18). ACM, 2018.

Digital Library

[14]

Matthias Christandl, Péter Vrana, and Jeroen Zuiddam. Barriers for Fast Matrix Multiplication from Irreversibility. In Amir Shpilka, editor, 34th Computational Complexity Conference (CCC 2019), volume 137, pages 26:1--26:17, 2019.

[15]

Zeev Dvir, János Kollár, and Shachar Lovett. Variety evasive sets. Comput. Complexity, 23(4):509--529, 2014.

[16]

Jordan S. Ellenberg and Dion Gijswijt. On large subsets of Fⁿ_q with no three-term arithmetic progression. Ann. of Math. (2), 185(1):339--343, 2017.

[17]

Yuval Filmus, Konstantin Golubev, and Noam Lifshitz. High dimensional hoffman bound and applications in extremal combinatorics. arXiv, 2019. arXiv:1911.02297.

[18]

Michael D. Fried and Moshe Jarden. Field arithmetic, volume 11 of Ergebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge. A Series of Modern Surveys in Mathematics. Springer-Verlag, Berlin, second edition, 2005.

[19]

W. T. Gowers and J. Wolf. Linear forms and higher-degree uniformity for functions on Fⁿ_q. Geom. Funct. Anal., 21(1):36--69, 2011.

[20]

Daniel R. Grayson and Michael E. Stillman. Macaulay2, a software system for research in algebraic geometry. Available at http://www.math.uiuc.edu/Macaulay2/.

[21]

Joe Harris. Algebraic geometry: a first course, volume 133. Springer Science & Business Media, 1992.

[22]

Oliver Janzer. Low analytic rank implies low partition rank for tensors. arXiv, 2018. arXiv: 1809.10931.

[23]

Oliver Janzer. Polynomial bound for the partition rank vs the analytic rank of tensors. arXiv, 2019. arXiv:1902.11207.

[24]

P. Koiran. Randomized and deterministic algorithms for the dimension of algebraic varieties. In Proceedings 38th Annual Symposium on Foundations of Computer Science, pages 36--45, October 1997.

[25]

Serge Lang and André Weil. Number of points of varieties in finite fields. Amer. J. Math., 76:819--827, 1954.

[26]

François Le Gall. Powers of tensors and fast matrix multiplication. In Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation (ISSAC 2014), pages 296--303, 2014.

[27]

Shachar Lovett. The analytic rank of tensors and its applications. Discrete Analysis, 2019.

[28]

Luka Milićević. Polynomial bound for partition rank in terms of analytic rank. Geometric and Functional Analysis, 29(5):1503--1530, 2019.

[29]

Eric Naslund and Will Sawin. Upper bounds for sunflower-free sets. In Forum of Mathematics, Sigma, volume 5. Cambridge University Press, 2017.

[30]

Sage. SageMath, the Sage Mathematics Software System (Version 8.1), 2017. URL: https://www.sagemath.org.

[31]

Volker Strassen. Relative bilinear complexity and matrix multiplication. J. Reine Angew. Math., 375/376:406--443, 1987.

[32]

Volker Strassen. The asymptotic spectrum of tensors. J. Reine Angew. Math., 384:102--152, 1988.

[33]

Volker Strassen. Degeneration and complexity of bilinear maps: some asymptotic spectra. J. Reine Angew. Math., 413:127--180, 1991.

[34]

Terence Tao. A symmetric formulation of the Croot-Lev-Pach-Ellenberg-Gijswijt capset bound, 2016. URL: https://terrytao.wordpress.com/2016/05/18/a-symmetric-formulation-of-the-croot-lev-pach-ellenberg-gijswijt-capset-bound.

[35]

B. L. van der Waerden. Algebra. Vol. I. Springer-Verlag, New York, 1991.

Cited By

Derksen HMakam VZuiddam J(2022)Subrank and optimal reduction of scalar multiplications to generic tensorsProceedings of the 37th Computational Complexity Conference10.4230/LIPIcs.CCC.2022.9(1-23)Online publication date: 20-Jul-2022
https://dl.acm.org/doi/10.4230/LIPIcs.CCC.2022.9
Cohen AMoshkovitz GKhuller SVassilevska Williams V(2021)Structure vs. randomness for bilinear mapsProceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing10.1145/3406325.3451007(800-808)Online publication date: 15-Jun-2021
https://dl.acm.org/doi/10.1145/3406325.3451007

Index Terms

Geometric rank of tensors and subrank of matrix multiplication
1. Mathematics of computing
2. Theory of computation

Recommendations

Powers of tensors and fast matrix multiplication
ISSAC '14: Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation

This paper presents a method to analyze the powers of a given trilinear form (a special kind of algebraic construction also called a tensor) and obtain upper bounds on the asymptotic complexity of matrix multiplication. Compared with existing approaches,...
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 ...
Group-theoretic algorithms for matrix multiplication
ISSAC '06: Proceedings of the 2006 international symposium on Symbolic and algebraic computation

The exponent of matrix multiplication is the smallest real number ω such that for all ε>0, O(n^ω+ε) arithmetic operations suffice to multiply two n×n matrices. The standard algorithm for matrix multiplication shows that ω≤3. Strassen's remarkable result [...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

CCC '20: Proceedings of the 35th Computational Complexity Conference

July 2020

1027 pages

ISBN:9783959771566

Conference Chair:
Luca Aceto
Gran Sasso Science Institute and Reykjavik University
,
Editor:
Shubhangi Saraf
Rutgers University, Piscatatway, NJ

In-Cooperation

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik

Dagstuhl, Germany

Publication History

Published: 08 October 2020

Check for updates

Author Tags

Qualifiers

Research-article

Conference

CCC '20

CCC '20: Computational Complexity Conference

July 28 - 30, 2020

Virtual Event, Germany

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 21 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Derksen HMakam VZuiddam J(2022)Subrank and optimal reduction of scalar multiplications to generic tensorsProceedings of the 37th Computational Complexity Conference10.4230/LIPIcs.CCC.2022.9(1-23)Online publication date: 20-Jul-2022
https://dl.acm.org/doi/10.4230/LIPIcs.CCC.2022.9
Cohen AMoshkovitz GKhuller SVassilevska Williams V(2021)Structure vs. randomness for bilinear mapsProceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing10.1145/3406325.3451007(800-808)Online publication date: 15-Jun-2021
https://dl.acm.org/doi/10.1145/3406325.3451007

View Options

Get Access

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

View options

Media

Figures

Other

Tables

View Table of Contents