Geometric rank of tensors and subrank of matrix multiplication

Open Access
Authors
Publication date 07-2020
Host editors
  • S. Saraf
Book title 35th Computational Complexity Conference
Book subtitle CCC 2020, July 28–31, 2020, Saarbrücken, Germany (Virtual Conference)
ISBN (electronic)
  • 9783959771566
Series Leibniz International Proceedings in Informatics
Event 35th Computational Complexity Conference, CCC 2020
Article number 35
Number of pages 21
Publisher Saarbrücken/Wadern: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Organisations
  • Interfacultary Research - Institute for Logic, Language and Computation (ILLC)
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.

Document type Conference contribution
Language English
Related publication Geometric Rank of Tensors and Subrank of Matrix Multiplication
Published at https://doi.org/10.48550/arXiv.2002.09472 https://doi.org/10.4230/LIPIcs.CCC.2020.35
Other links https://www.scopus.com/pages/publications/85089403946
Downloads
LIPIcs-CCC-2020-35 (Final published version)
Permalink to this page
Back