DROPS

Document

DOI: 10.4230/LIPIcs.CCC.2020.35

Geometric Rank of Tensors and Subrank of Matrix Multiplication

Authors: Swastik Kopparty, Guy Moshkovitz, and Jeroen Zuiddam

Published in: LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020)

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.

Cite as

Swastik Kopparty, Guy Moshkovitz, and Jeroen Zuiddam. Geometric Rank of Tensors and Subrank of Matrix Multiplication. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 35:1-35:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{kopparty_et_al:LIPIcs.CCC.2020.35,
  author =	{Kopparty, Swastik and Moshkovitz, Guy and Zuiddam, Jeroen},
  title =	{{Geometric Rank of Tensors and Subrank of Matrix Multiplication}},
  booktitle =	{35th Computational Complexity Conference (CCC 2020)},
  pages =	{35:1--35:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-156-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{169},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2020.35},
  URN =		{urn:nbn:de:0030-drops-125874},
  doi =		{10.4230/LIPIcs.CCC.2020.35},
  annote =	{Keywords: Algebraic complexity theory, Extremal combinatorics, Tensors, Bias, Analytic rank, Algebraic geometry, Matrix multiplication}
}

Search Results

Documents authored by Moshkovitz, Guy

Geometric Rank of Tensors and Subrank of Matrix Multiplication

Abstract

Cite as

Thanks for your feedback!

Could not send message