# Notions of Tensor Rank

Mandar Juvekar  Boston University, Boston, MA<EMAIL_ADDRESS>and  Arian
Nadjimzadah  UCLA, Los Angeles, CA<EMAIL_ADDRESS>
(Date: October 2022)

###### Abstract.

Tensors, or multi-linear forms, are important objects in a variety of areas
from analytics, to combinatorics, to computational complexity theory. Notions
of tensor rank aim to quantify the “complexity” of these forms, and are thus
also important. While there is one single definition of rank that completely
captures the complexity of matrices (and thus linear transformations), there
is no definitive analog for tensors. Rather, many notions of tensor rank have
been defined over the years, each with their own set of uses. In this paper we
survey the popular notions of tensor rank. We give a brief history of their
introduction, motivating their existence, and discuss some of their
applications in computer science. We also give proof sketches of recent
results by Lovett, and Cohen and Moshkovitz, which prove asymptotic
equivalence between three key notions of tensor rank over finite fields with
at least three elements.

##  1\. Introduction

We first come across the notion of rank in a course on linear algebra. If $A$
is an $m\times n$ matrix over a field $\operatorname{\mathbb{F}}$, the rank of
$A$ is the dimension of the space spanned by its rows (or columns). To help
generalize this definition, it will be useful to reinterpret the matrix $A$ as
a bilinear form
$T:\operatorname{\mathbb{F}}^{m}\times\operatorname{\mathbb{F}}^{n}\to\operatorname{\mathbb{F}}$
by the natural correspondence

$(x,y)\in\operatorname{\mathbb{F}}^{m}\times\operatorname{\mathbb{F}}^{n}\mapsto
T(x,y)=\sum_{i,j}A_{i,j}x^{i}y^{j}.$

As a notational convention, here and elsewhere in this paper we will use
superscripts to index coordinates of a vector, and subscripts to index over
different vectors. For example, if $x_{1},x_{2},\ldots$ are vectors,
$x_{5}^{7}$ would be the seventh coordinate of the fifth vector. Getting back
to ranks, using this correspondence, we can formulate an alternative
definition of rank where the rank of $T$ is the minimal natural number $r$
such that $T$ can be written as a sum of $r$ bilinear forms of “lowest”
complexity, or rank 1 matrices. The natural objects of lowest complexity are
the linear 1-forms, i.e., the dot product with a fixed vector. Products of
1-forms $T_{1}(x)T_{2}(y)$ are then bilinear forms. Since every bilinear form
can be written as a finite sum of forms of this type, we set them to be our
rank 1 bilinear forms (matrices). Putting everything together, our alternative
definition then says that the rank of a matrix $A$ is the minimum natural
number $r$ such that the bilinear form $T$ corresponding to $A$ can be written
as the sum of $r$ bilinear forms each of the type $T_{1}(x)T_{2}(y)$ where
$T_{1}$ and $T_{2}$ are 1-forms. This alternative definition agrees with the
usual linear algebra definition of rank (see for instance [Hal58, Sections 32
and 51]).

In this paper we focus on generalizing the notion of rank to higher-
dimensional analogs of matrices. What are these higher-dimensional matrices?
The higher-dimensional analogs we will look at are the $d$-tensors.

######  Definition 1.1 ($d$-tensor).

Let $\operatorname{\mathbb{F}}$ be a field. A _$d$ -tensor_ $T$ on
$\operatorname{\mathbb{F}}^{n_{1}}\times\cdots\times\operatorname{\mathbb{F}}^{n_{d}}$
is a multilinear map
$T:\operatorname{\mathbb{F}}^{n_{1}}\times\cdots\times\operatorname{\mathbb{F}}^{n_{d}}\to\operatorname{\mathbb{F}}$.

Note that a $d$-tensor
$T:\operatorname{\mathbb{F}}^{n_{1}}\times\cdots\times\operatorname{\mathbb{F}}^{n_{d}}\to\operatorname{\mathbb{F}}$
can naturally be identified with a $d$-dimensional array $M$ such that

$T(x_{1},\ldots
x_{d})=\sum_{i_{1}\in[n_{1}],\ldots,i_{d}\in[n_{d}]}M_{i_{1},\ldots,i_{d}}x_{1}^{i_{1}}\cdots
x_{d}^{i_{d}}.$

So, following the convention for matrices, we will often denote the space of
$d$-tensors on
$\operatorname{\mathbb{F}}^{n_{1}}\times\cdots\times\operatorname{\mathbb{F}}^{n_{d}}$
by $\operatorname{\mathbb{F}}^{n_{1}\times\cdots\times n_{d}}$.111Here and
elsewhere in the paper we will use $[n]$ to denote the set
$\\{1,2,\ldots,n\\}$.

The definition of rank given above generalizes well to arbitrary $d$-tensors.
Setting the rank 1 $d$-tensors to products of $d$ linear 1-forms (or, since
linear 1-forms are the same as 1-tensors, $d$ 1-tensors) leads to the notion
of rank that is traditionally associated with tensors. We call it _traditional
rank_ , or $\mathrm{TR}$ for short.

######  Definition 1.2 (Traditional Rank).

A $d$-tensor $T$ has _traditional rank 1_ if we can write

$T(x_{1},\ldots,x_{d})=T_{1}(x_{1})T_{2}(x_{2})\cdots T_{d}(x_{d}),$

where each $T_{j}$ is a 1-tensor.

The _traditional rank_ of an arbitrary $d$-tensor $T$, $\mathrm{TR}(T)$, is
the minimum number $r$ such that we can write

$T(x)=\sum_{i=1}^{r}T_{i}(x)$

where each $T_{i}$ is a $d$-tensor with traditional rank 1.

While this definition does generalize matrix rank it turns out that there are
also other, non-equivalent generalizations of matrix rank to arbitrary tensors
that characterize the combinatorial, analytic, and geometric properties of
tensors. Each of these notions is useful in its own way. Finding tight
relationships between these notions remains an open research question.

One disadvantage of the traditional notion of tensor rank is that it is
prohibitively hard to compute in general. Since Håstad’s work in 1989 [Hås89]
it has been known that computing traditional tensor rank over finite fields is
NP-complete, and over $\mathbb{Q}$ is NP-hard. In 2013 , Hillar and Lim [HL13]
showed that Håstad’s proof could be modified to show that traditional rank is
NP-hard over $\mathbb{R}$ and $\mathbb{C}$ as well. Traditional rank also
turns out to be NP-hard to approximate with arbitrarily small error bounds
[Swe18]. The non-traditional notions we will discuss are less “stringent” than
traditional rank, so it is possible that they are easier to compute. Showing
(exact or approximate) hardness results for those notions, however, is still
an open problem.

In this paper we introduce the landscape of notions of tensor rank, motivating
their existence (Section 2). We then give examples of applications of these
notions in computational complexity theory (Section 3). In Section 4 we give a
rundown of the trivial relationships between the notions that come from their
definitions. We then give sketches of results by Lovett [Lov19] (Section 5)
and Cohen and Moshkovitz [CM21] (Section 6) which, put together, prove
asymptotic equivalence between three key notions of rank over finite fields
with three or more elements.

##  2\. Tensor Rank Through the Ages

The oldest non-traditional notion of tensor rank is the so-called analytic
rank.

######  Definition 2.1 (Analytic Rank).

Let $\operatorname{\mathbb{F}}$ be a finite field. The _bias_ of a $d$-tensor
$T\in\operatorname{\mathbb{F}}^{n_{1}\times\cdots\times n_{d}}$ is given by

$\mathrm{bias}(T)=\operatorname{\mathbb{E}}_{(x_{1},\ldots,x_{d})\in\operatorname{\mathbb{F}}^{n_{1}}\times\cdots\times\operatorname{\mathbb{F}}^{n_{d}}}\chi(T(x_{1},\ldots,x_{d})),$

where $\chi$ is a nontrivial additive character which, in the case that
$\operatorname{\mathbb{F}}=\operatorname{\mathbb{F}}_{p}$, can be taken to be
$\chi(x)=e^{2\pi ix/p}$.

The _analytic rank_ of $T$, denoted by $\mathrm{AR}(T)$, is then given by

$\mathrm{AR}(T)=-\log_{\left\lvert\operatorname{\mathbb{F}}\right\rvert}\mathrm{bias}(T).$

This measure of the complexity of a tensor was first introduced by Gowers and
Wolf in the context of higher-order Fourier analysis [GW11]. In Section 5 we
will see the connection between the analytic rank and the other combinatorial
and geometric notions described below.

Going back to the traditional definition of tensor rank, there is no reason
why one cannot use other kinds of tensors as rank 1 tensors, as long as the
new notion agrees with the old in the case of matrices (in order to be a true
generalization). Doing so, it turns out, is useful for a whole host of
applications. The first such “alternative” notion was introduced in 2016 in
the context of the so-called “capset problem.”

A capset in $\mathbb{F}_{3}$ is a subset of $\mathbb{F}_{3}$ with no non-
trivial three-term arithmetic progressions. That is, a capset is a set
$A\subseteq\mathbb{F}_{3}$ that does not contain $\\{x,x+r,x+2r\\}$ for any
$x,r\in\mathbb{F}_{3}$ with $r\neq 0$. The capset problem asks what the
maximum size of a capset in $\mathbb{F}_{3}$ can be. In the spring of 2016,
Croot, Lev, and Pach [CLP17] proved a breakthrough result for a similar
problem in the additive group $\mathbb{Z}/4\mathbb{Z}$. They showed that if
$A\subseteq(\mathbb{Z}/4\mathbb{Z})^{n}$ contains no non-trivial three-term
arithmetic progressions, then $\left\lvert A\right\rvert\leq 3.60172^{n}$.
Soon after, Ellenberg and Gijswijt [EG17] generalized the Croot-Lev-Pach
argument to show that any progression-free set
$A\subseteq(\mathbb{Z}/p\mathbb{Z})^{n}$, where $p$ is a prime, satisfies
$\left\lvert A\right\rvert\leq(J(p)p)^{n}$ where $J(p)$ is an explicit
constant less than 1. This exponentially improved the known bound for the
capset problem, bringing it down from $O(3^{n}/n^{1+c})$ (where $c$ is some
absolute constant) to $O(2.756^{n})$. Tao [Tao16] reformulated the Ellenberg-
Gijswijt argument in terms of tensors, introducing what is now known as the
slice rank of a tensor.

######  Definition 2.2 (Slice Rank).

A $d$-tensor $T$ has _slice rank 1_ if we can write

$T(x_{1},\ldots,x_{d})=T_{1}(x_{i})T_{2}(x_{j}:j\neq i),$

where $i\in[d]$, $T_{1}$ is a 1-tensor, and $T_{2}$ is a $(d-1)$-tensor.

The _slice rank_ of an arbitrary $d$-tensor $T$, $\mathrm{SR}(T)$, is the
minimum number $r$ such that we can write

$T(x)=\sum_{i=1}^{r}T_{i}(x)$

where each $T_{i}$ is a $d$-tensor with slice rank 1.

Notice that in essence this definition just modifies Definition 1.2 so that
our rank 1 tensors go from being products of $d$ 1-tensors to being the
product of two tensors: one of order 1 and one of order $d-1$. Also notice
that in the case of matrices (which are 2-tensors), Definitions 2.2 and 1.2
are exactly the same and agree with the usual definition of matrix rank.

Slice rank, as we defined above, defines its rank 1 tensors by “slicing” off
one coordinate and multiplying a 1-tensor applied to that coordinate with a
$(d-1)$-tensor applied to the remaining coordinates. A natural extension to
this is to, instead of slicing off one coordinate, allow arbitrary partitions
of the coordinates into two parts. This was done in 2017 (preprint; published
in 2020) by Naslund [Nas20], who called this new notion of rank partition
rank. We formally define partition rank as follows.

######  Definition 2.3 (Partition Rank).

A $d$-tensor $T$ has _partition rank 1_ if we can write

$T(x_{1},\ldots,x_{d})=T_{1}(x_{i}:i\in S)T_{2}(x_{j}:j\notin S),$

where $S\subset[d]$ with $1\leq\left\lvert S\right\rvert<d$, $T_{1}$ is a
$\left\lvert S\right\rvert$-tensor, and $T_{2}$ is a $(d-\left\lvert
S\right\rvert)$-tensor.

The _partition rank_ of an arbitrary $d$-tensor $T$, $\mathrm{PR}(T)$, is the
minimum number $r$ such that we can write

$T(x)=\sum_{i=1}^{r}T_{i}(x)$

where each $T_{i}$ is a $d$-tensor with partition rank 1.

Using this new notion of rank, Naslund showed that any set
$A\subseteq\mathbb{F}_{q}^{n}$ with size bigger than
${n+(k-1)q\choose(k-1)(q-1)}$ must contain distinct vectors
$x_{1},x_{2},\ldots,x_{k+1}$ such that the vectors
$x_{1}-x_{k+1},x_{2}-x_{k+1},\ldots,x_{k}-x_{k+1}$ are mutually orthogonal (he
called a collection of such $x_{1},\ldots,x_{k+1}$ a $k$-right corner).

Our last, most recent notion of rank is motivated by an age-old, fundamental
question in computer science: asymptotically how many scalar additions and
multiplications are necessary to multiply two $n\times n$ matrices? Tensors
are naturally connected to this problem because the operation of matrix
multiplication itself can be thought of as a tensor.

Recall that matrices $M$ (2-tensors) can simultaneously be thought of as
bilinear forms
$T:\operatorname{\mathbb{F}}^{m}\times\operatorname{\mathbb{F}}^{n}\to\operatorname{\mathbb{F}}$
that map $(x,y)\mapsto x^{T}My$ and linear maps
$T^{\prime}:\operatorname{\mathbb{F}}^{m}\to\operatorname{\mathbb{F}}^{n}$
that map $x\mapsto Mx$. Similarly, we can also think of $d$-tensors

$T(x_{1},\ldots
x_{d})=\sum_{i_{1}\in[n_{1}],\ldots,i_{d}\in[n_{d}]}T_{i_{1},\ldots,i_{d}}x_{1}^{i_{1}}\cdots
x_{d}^{i_{d}}$

as $(d-1)$-linear maps
$T^{\prime}:\operatorname{\mathbb{F}}^{n_{1}}\times\cdots\times\operatorname{\mathbb{F}}^{n_{d-1}}\to\operatorname{\mathbb{F}}^{n_{d}}$
given by

$[T^{\prime}(x_{1},\ldots,x_{d-1})]_{k}=\sum_{i_{1}\in[n_{1}],\ldots,i_{d-1}\in[n_{d-1}]}T^{\prime}_{i_{1},\ldots,i_{d-1},k}x_{1}^{i_{1}}\cdots
x_{d-1}^{i_{d-1}}.$

By the usual formula for matrix multiplication, if $M$ and $N$ are $n\times n$
matrices over $\operatorname{\mathbb{F}}$, then $MN$ is an $n\times n$ matrix
with

$(MN)_{ij}=\sum_{\ell=1}^{n}M_{i\ell}N_{\ell j}.$

Identifying the space of $n\times n$ matrices with
$\operatorname{\mathbb{F}}^{n^{2}}$, the operation of matrix multiplication
takes two elements of $\operatorname{\mathbb{F}}^{n^{2}}$ to another element
of $\operatorname{\mathbb{F}}^{n^{2}}$ where each entry is a bilinear form
applied to $M$ and $N$. Thus matrix multiplication is a 3-tensor over the
space of $n\times n$ matrices. As we discuss in Section 3 the rank of this
tensor is intimately related to the computational complexity of matrix
multiplication.

Motivated by this application (as well as a few others), Kopparty, Moshkovitz,
and Zuiddam [KMZ20] recently introduced the notion of geometric rank. Unlike
the other types of ranks discussed, this notion of rank does not aim to
capture the combinatorial or analytic properties of the tensor. Rather, it
looks at the geometric properties of the tensor, defining rank as the
codimension of an algebraic variety. Kopparty, Moshkovitz, and Zuiddam used
this new notion of rank to prove tight bounds about the subrank of the matrix
multiplication tensor (the subrank is a quantity related to the rank that is
useful in the computational complexity analysis for matrix multiplication).

The geometric rank of a tensor is formally defined as follows.

######  Definition 2.4 (Geometric Rank).

Let $T\in\operatorname{\mathbb{F}}^{n_{1}\times\cdots\times n_{d}}$ be a
$d$-tensor with $d\geq 2$. The _geometric rank_ of $T$ is

$\displaystyle\mathrm{GR}(T)=\mathrm{codim}\\{(x_{1},\ldots,x_{d-1})$
$\displaystyle\in\operatorname{\mathbb{F}}^{n_{1}}\times\cdots\times\operatorname{\mathbb{F}}^{n_{d-1}}$
$\displaystyle:\forall z\in\operatorname{\mathbb{F}}^{n_{d}},\
T(x_{1},\ldots,x_{d-1},z)=0\\}.$

Here we use the usual definition of the codimension of an algebraic variety.
If $V\subseteq\operatorname{\mathbb{F}}^{n}$ is an algebraic variety (that is
possibly reducible), the dimension of $V$, $\dim(V)$, is defined to be the
length of a maximal chain of irreducible subvarieties of $V$. The codimension,
$\mathrm{codim}(V)$, is then defined to be $n-~{}\dim(V)$. For more detailed
explanations of these concepts we recommend looking at [Har13].

Geometric rank—as Kopparty, Moshkovitz, and Zuiddam mention without
proof—coincides with the linear algebra definition of matrix rank when $d=2$.
We give a quick proof of that here.

######  Proposition 2.5.

Let $M\in\operatorname{\mathbb{F}}^{m\times n}$ be a matrix (a 2-tensor), and
let $r$ be the rank of $M$ as per the linear algebra definition. Then
$r=\mathrm{GR}(M)$.

###### Proof.

By definition of geometric rank,

$\displaystyle\mathrm{GR}(M)$
$\displaystyle=\mathrm{codim}\\{x\in\operatorname{\mathbb{F}}^{m}:\forall
y\in\operatorname{\mathbb{F}}^{n}x^{T}My=0\\}$
$\displaystyle=\mathrm{codim}\\{x\in\operatorname{\mathbb{F}}^{m}:x^{T}M=\mathbf{0}^{T}\\}$
$\displaystyle=m-\dim\\{x\in\operatorname{\mathbb{F}}^{m}:x^{T}M=\mathbf{0}^{T}\\},$

where $\bf{0}$ is the zero vector in $\operatorname{\mathbb{F}}^{m}$. Notice
that $\dim\\{x\in\operatorname{\mathbb{F}}^{m}:x^{T}M\equiv\mathbf{0}^{T}\\}$
is just the nullity of $M$, and so by the rank nullity theorem we are done. ∎

There is a slight caveat to Definition 2.4, which is that it implicitly
assumes $\operatorname{\mathbb{F}}$ to be algebraically closed. This, however,
is not a problem because in a general field we can extend this definition via
the embedding of the field into its algebraic closure.

##  3\. Applications in Computer Science

Uttering the words “tensor rank” to a computer scientist will, with high
probability, elicit a response that contains the phrase “matrix
multiplication.” And for good reason; notions of tensor rank happen to be
intimately related to the complexity and efficient computation of matrix
multiplication.

Multiplying two matrices is a fundamental computation with applications in
nearly every field computers are used in. It is thus not surprising that the
following question is of great interest.

######  Question 3.1 (Arithmetic Complexity of Matrix Multiplication).

Given two $n\times n$ matrices $A$ and $B$ over a field
$\operatorname{\mathbb{F}}$, what is the minimum number of addition and scalar
multiplication operations needed to compute the $n\times n$ product matrix
$AB$ where

(1) $(AB)_{ij}=\sum_{\ell=1}^{n}A_{i\ell}B_{\ell j}?$

Can one find an algorithm that actually computes the product with that number
of operations?

The number of operations in Question 3.1 is known as the arithmetic complexity
of $n\times n$ matrix multiplication. Let us call this number
$\mathcal{A}(n)$. An exact determination of $\mathcal{A}(n)$ seems to be
outside the range of methods available at the present time, so much of the
work around this has been focused on getting asymptotic bounds on arithmetic
complexity. It is then useful to define the following quantity.

######  Definition 3.2 (Exponent of Matrix Multiplication).

The _exponent of matrix multiplication_ , $\omega$, is defined as

$\omega=\inf\\{\tau\in\mathbb{R}:\mathcal{A}(n)=O(n^{\tau})\\}.$

Equivalently,

$\displaystyle\omega=\inf\\{\tau:\exists\text{ an algorithm to compute
}n\times n\text{ MM with }O(n^{\tau})\text{ operations}\\}.$

It is easy to see that $\omega\in[2,3]$. The upper bound comes from the fact
that the naïve algorithm of computing each entry of the product using Equation
1 is $O(n^{3})$. The lower bound holds because any algorithm for matrix
multiplication would have to make at least $n^{2}$ computations since the
output is an $n\times n$ matrix. A long-standing conjecture in algebraic
complexity theory is that $\omega$ is in fact equal to 2.

As mentioned in Section 2, the operation of matrix multiplication is itself a
3-tensor. It is convention to denote the tensor to multiply a $k\times m$
matrix and an $m\times n$ matrix with $\left\langle k,m,n\right\rangle$. Since
we are only focusing on square matrices, we will focus on the tensors
$\left\langle n,n,n\right\rangle$, which we will often shorten to
$\operatorname{\langle n\rangle}$. Seeing as rank is supposed to encode the
complexity of a tensor, it is not surprising that it is closely connected to
$\mathcal{A}(n)$. The following result is known to hold.

######  Theorem 3.3.

Over any field, we have

$\omega=\inf\\{\tau\in\mathbb{R}:\mathrm{TR}(\operatorname{\langle
n\rangle})=O(n^{\tau})\\}.$

###### Proof.

See [BCS97, Proposition 15.1] ∎

An important application of Theorem 3.3 is in showing that the exponent of
matrix multiplication does not change under another important, related measure
of complexity called the multiplicative complexity of matrix multiplication.
The multiplicative complexity of matrix multiplication is defined as the
minimum number of scalar multiplication operations required for $n\times n$
matrix multiplication (the algorithm is of course also allowed additions). Let
us call this quantity $\mathcal{M}(n)$. It has been shown that $\mathcal{M}$
relates to traditional tensor rank in the following way (see, for instance,
[BCS97, Section 14.1]).

$\frac{1}{2}\mathrm{TR}(\operatorname{\langle
n\rangle})\leq\mathcal{M}(n)\leq\mathrm{TR}(\operatorname{\langle n\rangle}).$

From this inequality it follows that $\mathrm{TR}(\operatorname{\langle
n\rangle})=O(n^{\tau})$ implies $\mathcal{M}(n)=O(n^{\tau})$ and
$\mathcal{M}(n)=O(n^{\tau})$ implies $\mathrm{TR}(\operatorname{\langle
n\rangle})=O(n^{\tau})$. Combining this with Theorem 3.3 gives us
$\omega=\inf\\{\tau\in\mathbb{R}:\mathcal{M}(n)=O(n^{\tau})\\}$.

The connection in Theorem 3.3 also implies that upper and lower bounds on
$\mathrm{TR}$ directly translate to upper and lower bounds on the exponent of
matrix multiplication. The following result makes this explicit.

######  Theorem 3.4 ([Blä13]).

If $\mathrm{TR}(\left\langle k,m,n\right\rangle)\leq r$, then
$\omega\leq\log_{kmn}r$.

In his seminal work, Strassen [Str69] showed that square matrices of size 2
can be multiplied with seven multiplication operations (as opposed to eight
using the naïve method) at the cost of a few more addition operations. It
follows from his work that $\mathrm{TR}(\left\langle 2\right\rangle)\leq 7$.
Plugging this into Theorem 3.4 tells us that $\omega\leq
3\log_{8}7=\log_{2}7=2.801...\leq 2.81$. Hopcroft and Kerr [HK71] and Winograd
[Win71] later (independently) showed that $2\times 2$ multiplication is not
possible with just six multiplications, which implies that
$\mathrm{TR}(\left\langle 2\right\rangle)$ is in fact equal to 7. Thus
$\log_{2}7$ is the sharpest bound one can get from Theorem 3.4 using
$\left\langle 2\right\rangle$. It turns out that $\mathrm{TR}(\left\langle
70\right\rangle)\leq 143.640$ [Pan80], which gives a slightly better bound of
2.80. Whether other tensors can lead to sharper bounds remains an open
question.

Strassen [Str86], using more traditional-rank-related techniques, was able to
prove that $\omega<2.48$. Coppersmith and Winograd [CW87], using a
construction of arithmetic-progression-free sets, showed that $\omega\leq
2.375...$. Starting in 2010, by analyzing higher-order variants of the
Coppersmith-Winograd construction, Stothers [Sto10], then Vassilevska Willians
[Wil12], and then Le Gall [LG14] made incremental improvements. This led to
the current best upper bound of $\omega<2.372...$.

The connections between matrix multiplication and tensor rank do not end here.
As mentioned in the previous paragraph, Coppersmith and Winograd’s proof
involved a construction of arithmetic-progression-free sets. This suggests
that the complexity of matrix multiplication might be related to the capset
problem and Tao’s slice rank. And indeed, that did turn out to be the case. In
2003, Cohn and Umans [CU03] described a framework for proving upper bounds on
$\omega$ that involves reducing matrix multiplication to group algebra
multiplication. In 2012, Alon, Shpilka, and Umans [ASU12] proved relations
between various then-open conjectures in combinatorics and bounds on $\omega$.
The resolution of the capset problem in 2016 settled some of the conjectures
involved in the 2012 work. That led to the 2017 work of Blasiak et al.
[BC+17], which used the resolution of the capset problem to rule out obtaining
an $\omega=2$ using a subclass of Cohn-Umans-style constructions. In doing so,
they extended the capset result, making extensive use of the notion of slice
ranks.

Finally, the introduction of the geometric rank was in part motivated by the
complexity of matrix multiplication. In particular, Kopparty, Moshkovitz, and
Zuiddam [KMZ20] used the notion of geometric rank to prove a tight upper bound
on the so-called border subrank of the matrix multiplication tensor, which
matched a known lower bound. While the exact definitions of subrank are beyond
the scope of this survey, we recommend reading [KMZ20] for further details.

##  4\. Some Trivial Relationships

Before getting to the deeper connections between the different notions of
rank, we state some consequences obvious from the definitions. Any rank 1 form
used in Definition 2.2,

$T_{1}(x_{1})T_{2}(x_{j}:j\neq i),$

is in particular a rank 1 form of the form in Definition 2.3,

(2) $T_{1}(x_{i}:i\in S)T_{2}(x_{j}:j\notin S).$

A tensor of the form in (2) is in turn of the form of the rank 1 form in
Definition 1.2,

$T_{1}(x_{1})\cdots T_{d}(x_{d}).$

This implies the following result.

######  Proposition 4.1.

For any tensor $T$,

$\mathrm{PR}(T)\leq\mathrm{SR}(T)\leq\mathrm{TR}(T).$

##  5\. Relating Analytic Rank to the Others

We now discuss some deeper relationships which will show a cycle of
relationships between $\mathrm{AR}$, $\mathrm{SR}$, and $\mathrm{TR}$. We
start with an elegant result due to Lovett relating the analytic and partition
rank. For ease of notation we will look at tensors
$T:V^{d}\to\operatorname{\mathbb{F}}$ where $V=\operatorname{\mathbb{F}}^{n}$
for some $n$. It will be easy to see that this proof can be generalized to
arbitrary $T\in\operatorname{\mathbb{F}}^{n_{1}\times\cdots\times n_{d}}$.

######  Theorem 5.1 ([Lov19]).

Let $T:V^{d}\to\operatorname{\mathbb{F}}$ be a $d$-tensor. Then
$\mathrm{AR}(T)\leq\mathrm{PR}(T)$.

To prove this theorem we will need a lemma as well as another theorem about
the arithmetic rank. Both of these are due to Lovett.

######  Lemma 5.2 ([Lov19]).

For each $I\subseteq[d]$ let $R_{I}:V^{\left\lvert
I\right\rvert}\to\operatorname{\mathbb{F}}$ be an $\left\lvert
I\right\rvert$-tensor. Let

$R(x)=\sum_{I\subseteq[d]}R_{I}(x_{j}:j\in I).$

Then $\left\lvert\mathrm{bias}(R)\right\rvert\leq\mathrm{bias}(R_{[d]})$.

###### Proof.

First, let $W_{0},\ldots,W_{n}$ be arbitrary functions from
$\operatorname{\mathbb{F}}^{m}$ to $\operatorname{\mathbb{F}}$. Let $A$ and
$B$ be functions from
$\operatorname{\mathbb{F}}^{n}\times\operatorname{\mathbb{F}}^{m}$ to
$\operatorname{\mathbb{F}}$ defined by

$\displaystyle A(x,y)$ $\displaystyle=\sum_{i=1}^{n}x^{i}W_{i}(y),\text{ and}$
$\displaystyle B(x,y)$ $\displaystyle=A(x,y)+W_{0}(y).$

From the definition of bias we get

$\displaystyle\mathrm{bias}(B)$
$\displaystyle=\operatorname{\mathbb{E}}_{x,y}\chi(B(x,y))$
$\displaystyle=\operatorname{\mathbb{E}}_{x,y}\chi(A(x,y)+W_{0}(y))$
$\displaystyle=\operatorname{\mathbb{E}}_{x,y}[\chi(A(x,y))\cdot\chi(W_{0}(y))]$
$\displaystyle=\operatorname{\mathbb{E}}_{y}[\chi(W_{0}(y))\cdot\operatorname{\mathbb{E}}_{x}\chi(\sum_{i=1}^{n}x^{i}W_{i}(y))]$
$\displaystyle=\operatorname{\mathbb{E}}_{y}[1_{W_{1}(y)=\cdots=W_{n}(y)=0}\chi(W_{0}(y))],$

where the last equality holds because the expectation over $x$ is 0 whenever
any of the $W_{j}$ with $1\leq j\leq n$ are non-zero. Taking absolute values
and using the triangle inequality gives us

(3)
$\left\lvert\mathrm{bias}(B)\right\rvert\leq\operatorname{\mathbb{E}}_{y}[1_{W_{1}(y)=\cdots=W_{n}(y)=0}]=\mathrm{bias}(A).$

With this smaller result, we prove the lemma by applying it repeatedly. Fixing
$i\in[d]$, we can break up the summation in the definition of $R$ as follows.

$R(x)=\sum_{I\subseteq[d];i\in I}R_{I}(x_{j}:j\in
I)+\sum_{I\subseteq[d];i\notin I}R_{I}(x_{j}:j\in I).$

Notice that each $R_{I}(x_{j}:j\in I)$ where $i\in I$ is a tensor depending on
$x_{i}$, and thus can be written as $x_{i}^{j}W_{j}(x_{k}:k\neq i)$. Thus the
first sum is of the form $\sum_{j}x_{i}^{j}W_{j}(y)$, which matches the form
of $A$ above. The second sum does not depend on $x_{i}$, and so is of the form
of $B$. Thus, applying Equation 3 gives us

$\left\lvert\mathrm{bias}(R)\right\rvert\leq\mathrm{bias}\left(\sum_{I\subseteq[d];i\in
I}R_{I}(x_{j}:j\in I)\right).$

We use this inequality iteratively. First, applying it for $i=d$ we have

$\left\lvert\mathrm{bias}(R)\right\rvert\leq\mathrm{bias}\left(\sum_{I\subseteq[d];d\in
I}R_{I}(x_{j}:j\in I)\right).$

Using $\sum_{I\subseteq[d];d\in I}R_{I}(x_{j}:x_{j}\in I)$ instead of the
tensor $R$ in our inequality with $i=d-1$ gives us

$\left\lvert\mathrm{bias}\left(\sum_{I\subseteq[d];d\in I}R_{I}(x_{j}:j\in
I)\right)\right\rvert\leq\mathrm{bias}\left(\sum_{I\subseteq[d-1];d-1\in
I;d\in I}R_{I}(x_{k}:k\in I)\right).$

Continuing this process and applying the inequality for $d-2,\ldots,1$, and
then chaining the inequalities gives us

$\displaystyle\left\lvert\mathrm{bias}(R)\right\rvert\leq\mathrm{bias}(R_{[d]})$

as desired. ∎

Using this lemma, Lovett proves that the analytic rank is sub-additive.

######  Theorem 5.3 ([Lov19]).

Let $T,S:V^{d}\to\operatorname{\mathbb{F}}$ be $d$-tensors. Then

$\mathrm{AR}(T+S)\leq\mathrm{AR}(T)+\mathrm{AR}(S).$

###### Proof Sketch.

For this proof, Lovett defines functions $T_{I}$ and $S_{I}$ such that for any
$x,y$, $T(x,y)=\sum_{I\subseteq[d]}T_{I}(x_{I},y_{[d]-I})$ (similarly for $S$)
where $x_{I}=(x_{i}:i\in I)$ (similarly for $y$). Using this decomposition and
performing some algebra leads to

$\displaystyle\mathrm{bias}(T)\mathrm{bias}(S)\leq\left\lvert\mathrm{bias}\left((T+S)(x)+\sum_{I\subsetneq[d]}S_{I}(x_{I},b_{[d]-I})\right)\right\rvert,$

where $b$ is a fixed choice for $y$.

Applying Lemma 5.2 to the functions $R_{[d]}=(T+S)(x)$ and
$R_{I}=S_{I}(x_{I},b_{[d]-I})$ shows that the right hand side of the
inequality is less than or equal to $\mathrm{bias}(R{[d]})$, which in our case
equals $\mathrm{bias}(T+S)$. Putting everything together we get

$\mathrm{bias}(T+S)\geq\mathrm{bias}(T)\mathrm{bias}(S),$

and so by the definition of analytic rank,

$\displaystyle\mathrm{AR}(T+S)\leq\mathrm{AR}(T)\mathrm{AR}(S).$

∎

Using these two results, we can now prove Theorem 5.1.

###### Proof of Theorem 5.1.

Given Theorem 5.3, it suffices to prove Theorem 5.1 for tensors of partition
rank 1. So suppose $T:V^{d}\to\operatorname{\mathbb{F}}$ has partition rank 1.
Then we can find a partition $A\sqcup B=[d]$ with $\left\lvert
A\right\rvert,\left\lvert B\right\rvert\geq 1$ such that

$T(x)=T_{1}(x_{i}:i\in A)T_{2}(x_{j}:j\in B).$

For convenience, let us denote $(x_{i}:i\in A)$ by $x_{A}$ and $(x_{j}:j\in
B)$ by $x_{B}$.

Since the partition rank of $T$ is 1, we need to show that $\mathrm{AR}(T)\leq
1$. To do so, it suffices to show (by definition of analytic rank) that
$\mathrm{bias}(T)\geq\left\lvert\operatorname{\mathbb{F}}\right\rvert^{-1}$.
For any $a,b\in\operatorname{\mathbb{F}}$ define the function

$\displaystyle F_{a,b}(x)=(T_{1}(x_{A})+a)(T_{2}(x_{B})+b).$

Expanding it out we can write

$\displaystyle F_{a,b}(x)$
$\displaystyle=T_{1}(x_{A})T_{2}(x_{B})+T_{1}(x_{A})b+T_{2}(x_{B})a+ab$
$\displaystyle=T(x)+T_{1}(x_{A})b+T_{2}(x_{B})a+ab.$

Letting $R_{A}(x)=T_{1}(x_{A})b$, $R_{B}(x)=T_{2}(x_{B})a$,
$R_{\emptyset}=ab$, and $R_{[d]}=T$, we can apply Lemma 5.2 to get

$\displaystyle\left\lvert\mathrm{bias}(F_{a,b})\right\rvert\leq\mathrm{bias}(T).$

On the other hand, if $a$ and $b$ are chosen uniformly, we can take the
expectation of the bias over $a$ and $b$ to get

$\displaystyle\operatorname{\mathbb{E}}_{a,b}\mathrm{bias}(F_{a,b})$
$\displaystyle=\operatorname{\mathbb{E}}_{a,b\in F;x\in
V^{d}}[\chi((T_{1}(x_{A})+a)(T_{2}(x_{B})+b))]$
$\displaystyle=\operatorname{\mathbb{E}}_{a,b\in\operatorname{\mathbb{F}}}[\chi(ab)]$
$\displaystyle=\mathrm{Pr}_{b\in\operatorname{\mathbb{F}}}[b=0]$
$\displaystyle=\left\lvert\operatorname{\mathbb{F}}\right\rvert^{-1}.$

This proves our theorem. ∎

Combining Theorem 5.1 with Proposition 4.1 gives us the following corollary.

######  Corollary 5.4.

Let $T:V^{d}\to\operatorname{\mathbb{F}}$ be a $d$-tensor. Then
$\mathrm{AR}(T)\leq\mathrm{SR}(T)$.

##  6\. Closing the Loop for 3-tensors: Cohen and Moshkovitz’s Argument

Cohen and Moshkovitz [CM21] proved the following two theorems which, for
3-tensors over finite fields with at least 3 elements, show asymptotic
equivalence between $\mathrm{AR}$, $\mathrm{GR}$, and $\mathrm{SR}$ when
combined with Lovett’s result.

######  Theorem 6.1 ([CM21]).

For any $3$-tensor $T$ over a perfect field $\operatorname{\mathbb{F}}$,

$\mathrm{SR}(T)\leq 3\mathrm{GR}(T)$

######  Theorem 6.2 ([CM21]).

For any 3-tensor $T$ over any finite field $\operatorname{\mathbb{F}}$,

$\mathrm{AR}(T)\geq(1-\log_{\left\lvert\operatorname{\mathbb{F}}\right\rvert}2)\mathrm{GR}(T).$

Our goal will be to give an intuitive sketch of their argument. Techniques
from algebraic geometry will be essential, so we give some background.

###  6.3. Background from Algebraic Geometry

From now on, let $\mathbb{K}$ be a field. Recall that a _variety cut out by a
(finite) number of polynomials_ over $\mathbb{K}^{n}$ is the subspace of
$\mathbb{K}^{n}$ where all the polynomials vanish. The ideal $I(V)$ of a
variety $V$ is defined as follows.

######  Definition 6.4 (Ideal of a Variety).

Let $V\subset\mathbb{K}^{n}$ be a variety. The _ideal_ of $V$ is

$I(V)=\\{f\in\mathbb{K}[x]:f(p)=0\text{ for each }p\in V\\}.$

Now we define the tangent space $T_{p}V$ to a variety $V$ at $p$.

######  Definition 6.5 (Tangent Space).

Let $V\subset\mathbb{K}^{n}$ be a variety. The _tangent space_ $T_{p}V$ to a
variety $V$ at $p$ is

$T_{p}V=\left\\{\mathbf{v}\in\mathbb{K}^{n}:\frac{\partial
g}{\partial\mathbf{v}}(p)=0,\text{ for each }g\in I(V)\right\\}.$

One can check that any variety can be written uniquely as the union of
_irreducible varieties_. An irreducible variety is one which cannot be written
as the union of strictly contained subvarieties. Then the _dimension_ of a
variety $V$ can be defined as follows.

######  Definition 6.6 (Dimension of a Variety).

The _dimension_ of a variety $V\subset\mathbb{K}^{n}$, written $\dim V$, is
the maximal length of a chain of irreducible varieties such that

$\emptyset\neq V_{1}\subsetneq V_{2}\subsetneq\cdots\subsetneq V_{k}\subsetneq
V.$

The _codimension_ of a variety $V\subset\mathbb{K}^{n}$, $\mathrm{codim}V$, is

$\mathrm{codim}V=n-\dim V.$

###  6.7. Proof Sketch of Theorem 6.1

For the full argument see [CM21]. We will give a broader overview of the proof
with the aim of conveying the intuition.

The proof of Theorem 6.1 hinges on the following previously proved rephrasing
of geometric rank.

######  Lemma 6.8.

For a 3-tensor over any field $\mathbb{K}$,

$\mathrm{GR}(T)=\min_{r}\\{r+\mathrm{codim}\\{x:\mathrm{rank}\
T(x,\cdot,\cdot)=r\\}\\}.$

###### Proof.

See [KMZ20, Theorem 3.1]. ∎

Let $r$ achieve the minimum in Lemma 6.8. Defining

$X_{r}=\\{x\in\overline{\operatorname{\mathbb{F}}}^{n_{1}}:\mathrm{rank}T(x,\cdot,\cdot)\leq
r\\},$

one can use Lemma 6.8 to show that $\mathrm{GR}(T)=r+\mathrm{codim}X_{r}$. A
3-tensor $T$ with encoding array $(T_{i,j,k})$ can be reinterpreted as a
linear space $L\subset\overline{\operatorname{\mathbb{F}}}^{n_{1}\times
n_{2}}$ spanned by $\\{M_{1},\ldots,M_{n_{3}}\\}$, where
$M_{k}=(T_{i,j,k})_{i,j}$. One also has an association going the other way.
Given a matrix space $L$, choose a basis $M_{1},\ldots,M_{k}$, and let $T$ be
the tensor with encoding array $(M_{1},\ldots,M_{k})$. Thus the notions of
rank for tensors can be transferred to matrix spaces.

Now let

$L_{r}=L\cap M_{r},$

where $M_{r}$ is the space of $n_{1}\times n_{2}$ matrices of rank at most
$r$. Note that $M_{r}$, being the space cut out by the $(r+1)\times(r+1)$
minors, is itself a variety. It turns out that the variety $X_{r}$ is
isomorphic to $L_{r}\times\overline{\operatorname{\mathbb{F}}}^{n_{1}-d}$.
Thus $\mathrm{codim}X_{r}=\mathrm{codim}_{L}L_{r}$.222Here
$\mathrm{codim}_{L}X$ is the codimension of a variety $X$ in a linear space
$L$, i.e. $\mathrm{codim}_{L}X=\dim L-\dim X$. We have reduced the problem to
analyzing these “slices” of the matrix space $L$. Above,
$\overline{\operatorname{\mathbb{F}}}$ is the algebraic closure of
$\operatorname{\mathbb{F}}$, which will be easier to work over in the
arguments to follow. We let $\overline{\mathrm{SR}}(T)$ be as in Definition
2.2, except the coefficients are allowed to come from
$\overline{\operatorname{\mathbb{F}}}$. Clearly
$\overline{\mathrm{SR}}(T)\leq\mathrm{SR}(T)$. One also has
$2\mathrm{SR}(T)\leq 3\overline{\mathrm{SR}}(T)$ which is proved in [CM21].

We would be done if we had the following.

######  Lemma 6.9.

Let $L\subset\mathbb{K}^{m\times n}$ be a matrix space over any algebraically
closed field $\mathbb{K}$. For any $r\in\mathbb{N}$,

$\mathrm{SR}(L)\leq 2r+\mathrm{codim}_{L}L_{r}.$

To see this, observe that

$\displaystyle\overline{\mathrm{SR}}(T)$ $\displaystyle=\mathrm{SR}(L)\leq
2r+\mathrm{codim}_{L}L_{r}$ $\displaystyle=2r+\mathrm{codim}X_{r}$
$\displaystyle=2\mathrm{GR}(T)-\mathrm{codim}X_{r}$ $\displaystyle\leq
2\mathrm{GR}(T).$

Applying $2\mathrm{SR}(T)\leq 3\overline{\mathrm{SR}}(T)$ gives
$\mathrm{SR}(T)\leq 3\mathrm{GR}(T)$.

###### Proof sketch of Lemma 6.9.

We proceed by induction. The base case is $\mathrm{SR}(L)\leq\dim L$, which is
not difficult to show. Now consider the inductive step. Let $V$ be an
irreducible component of $L_{r}$ with $\dim V=\dim L_{r}$, and $A\in
V\setminus M_{r-1}$. If $V\setminus M_{r-1}=\emptyset$ then we have
$V\subseteq L_{r-1}$, and the result follows from induction. So we assume
$V\setminus M_{r-1}\neq\emptyset$. The trick now is to decompose the matrix
space $L$ into subspaces $P=L\cap T_{A}M_{r}$ and $P^{\perp}$. This particular
decomposition is useful because one can run an explicit calculation to find
that

$\mathrm{SR}(T_{A}M_{r})\leq 2r.$

We need the following simple properties of slice rank and tangent spaces to
conclude the result from that calculation.

######  Lemma 6.10.

  1. (1)

$\mathrm{SR}(L)\leq\dim L$.

  2. (2)

$\mathrm{SR}(L^{\prime})\leq\mathrm{SR}(L)$ if $L^{\prime}\subset L$.

  3. (3)

$\mathrm{SR}(L+L^{\prime})\leq\mathrm{SR}(L)+\mathrm{SR}(L^{\prime})$.

  4. (4)

$T_{p}(V\cap W)\subset T_{p}V\cap T_{p}W$.

  5. (5)

If $V$ is irreducible and $p\in V$ then $\dim V\leq\dim T_{p}V$.

Using Lemma 6.10 and the main estimate $\mathrm{SR}(T_{A}M_{r})\leq 2r$,

$\mathrm{SR}(P)=\mathrm{SR}(L\cap T_{A}M_{r})\leq\mathrm{SR}(T_{A}M_{r})\leq
2r.$

We also have

$\displaystyle\dim L_{r}$ $\displaystyle\leq\dim T_{A}V$
$\displaystyle\leq\dim T_{A}L_{r}$ $\displaystyle\leq\dim(T_{A}L\cap
T_{A}M_{r})$ $\displaystyle\leq\dim(L\cap T_{A}M_{r})=\dim P.$

Thus we have $\mathrm{codim}_{L}P\leq\mathrm{codim}_{L}L_{r}$. Using Lemma
6.10 we get

$\mathrm{SR}(P^{\perp})\leq\mathrm{codim}_{L}P\leq\mathrm{codim}_{L}L_{r}.$

Hence

$\displaystyle\mathrm{SR}(L)$ $\displaystyle=\mathrm{SR}(P+P^{\perp})$
$\displaystyle\leq\mathrm{SR}(P)+\mathrm{SR}(P^{\perp})$ $\displaystyle\leq
2r+\mathrm{codim}_{L}L_{r}.$

∎

###  6.11. Proof Sketch of Theorem 6.2

The key ingredient of the proof is the following generalization of the
Schwarz-Zippel lemma. Define
$V(\operatorname{\mathbb{F}})=V\cap\operatorname{\mathbb{F}}^{n}$ for a
variety $V\subset\overline{\operatorname{\mathbb{F}}}^{n}$ defined over
$\operatorname{\mathbb{F}}$.

######  Lemma 6.12.

For any variety $V\subset\overline{\operatorname{\mathbb{F}}}^{n}$ defined
over any finite field $\operatorname{\mathbb{F}}$ cut out by polynomials of
degree at most $d$,

$\frac{|V(\operatorname{\mathbb{F}})|}{|\operatorname{\mathbb{F}}|^{n}}\leq\left(\frac{d}{|\operatorname{\mathbb{F}}|}\right)^{\mathrm{codim}V}.$

We use Lemma 6.12 to prove Theorem 6.2. Consider
$T\in\operatorname{\mathbb{F}}^{n_{1}\times n_{2}\times n_{3}}$, where we
interpret $T$ as its defining array. Set
$V=\ker(T)\subset\overline{\operatorname{\mathbb{F}}}^{N}$ with
$N=n_{1}+n_{2}$, where here we use the bilinear map formulation of $T$. By
Lemma 6.12,

$\frac{|V(\operatorname{\mathbb{F}})|}{|\operatorname{\mathbb{F}}|^{n}}\leq\left(\frac{d}{|\operatorname{\mathbb{F}}|}\right)^{\mathrm{codim}V},$

since $T$ is bilinear. Thus

$\displaystyle\mathrm{AR}(T)$
$\displaystyle=-\log_{|\operatorname{\mathbb{F}}|}\frac{|V(\operatorname{\mathbb{F}})|}{|\operatorname{\mathbb{F}}|^{N}}$
(Using Lemma 6.12)
$\displaystyle\geq\mathrm{codim}V\cdot(1-\log_{|\operatorname{\mathbb{F}}|}2)$
$\displaystyle=\mathrm{GR}(T)(1-\log_{|\operatorname{\mathbb{F}}|}2).$

The first equality above is true since

$\displaystyle\mathrm{bias}(T)$
$\displaystyle=\operatorname{\mathbb{E}}_{(x_{1},x_{2})\in\operatorname{\mathbb{F}}^{n_{1}}\times\operatorname{\mathbb{F}}{n_{2}}}\left[\operatorname{\mathbb{E}}_{x_{3}\in
F^{n_{3}}}\chi(T(x_{1},x_{2},x_{3}))\right]$ (4)
$\displaystyle=\Pr_{(x_{1},x_{2})\in\operatorname{\mathbb{F}}^{n_{1}}\times\operatorname{\mathbb{F}}{n_{2}}}[T(x_{1},x_{2},\cdot)\equiv
0]$
$\displaystyle=\frac{|V(\operatorname{\mathbb{F}})|}{|\operatorname{\mathbb{F}}|^{N}}.$

Equation 4 holds because the bias of a linear form is 0 unless the linear form
is identically 0, in which case its bias is 1. ∎

## Acknowledgements

We would like to thank Alex Iosevich and Kaave Hosseini for their invaluable
discussions while exploring this material, and for their advice during the
writing process. This work was done while both authors were undergraduate
students at the University of Rochester.

## References

  * [ASU12] Noga Alon, Amir Shpilka, and Christopher Umans.  On sunflowers and matrix multiplication.  In 2012 IEEE 27th Conference on Computational Complexity, pages 214–223. IEEE, 2012.
  * [BC+17] Jonah Blasiak, , Thomas Church, Henry Cohn, Joshua A. Grochow, Eric Naslund, William F. Sawin, and Chris Umans and.  On cap sets and the group-theoretic approach to matrix multiplication.  Discrete Analysis, January 2017.
  * [BCS97] Peter Bürgisser, Michael Clausen, and M. Amin Shokrallahi.  Algebraic complexity theory.  Springer-Verlag Berlin Heidelberg, 1997.
  * [Blä13] Markus Bläser.  Fast matrix multiplication.  Theory of Computing, pages 1–60, 2013.
  * [CLP17] Ernie Croot, Vsevolod Lev, and Péter Pach.  Progression-free sets in $\mathbb{Z}^{n}_{4}$ are exponentially small.  Annals of Mathematics, 185(1):331 – 337, 2017.
  * [CM21] Alex Cohen and Guy Moshkovitz.  Structure vs. randomness for bilinear maps.  In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 800–808, 2021.
  * [CU03] Henry Cohn and Christopher Umans.  A group-theoretic approach to fast matrix multiplication.  In 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings. IEEE Computer. Soc, 2003.
  * [CW87] Don Coppersmith and Shmuel Winograd.  Matrix multiplication via arithmetic progressions.  In Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, STOC ’87, page 1–6, New York, NY, USA, 1987. Association for Computing Machinery.
  * [EG17] Jordan Ellenberg and Dion Gijswijt.  On large subsets of $\mathbb{F}^{n}_{q}$ with no three-term arithmetic progression.  Annals of Mathematics, 185(1):339 – 343, 2017.
  * [GW11] William Gowers and Julia Wolf.  Linear forms and higher-degree uniformity for functions on $\mathbb{F}_{p}^{n}$.  Geometric and Functional Analysis, 21(1):36–69, 2011.
  * [Hal58] Paul Halmos.  Finite-dimensional vector spaces.  Van Nostrand, Princeton, NJ, 2nd ed. edition, 1958.
  * [Har13] Joe Harris.  Algebraic geometry: a first course, volume 133.  Springer Science & Business Media, 2013.
  * [Hås89] Johan Håstad.  Tensor rank is np-complete.  In International Colloquium on Automata, Languages, and Programming, pages 451–460. Springer, 1989.
  * [HK71] John Hopcroft and Leslie Kerr.  On minimizing the number of multiplications necessary for matrix multiplication.  SIAM Journal on Applied Mathematics, 20(1):30–36, 1971.
  * [HL13] Christopher J. Hillar and Lek-Heng Lim.  Most tensor problems are np-hard.  J. ACM, 60(6), nov 2013.
  * [KMZ20] Swastik Kopparty, Guy Moshkovitz, and Jeroen Zuiddam.  Geometric rank of tensors and subrank of matrix multiplication.  In Proceedings of the 35th Computational Complexity Conference (CCC 2020), Leibniz International Proceedings in Informatics (LIPIcs), pages 35:1–35:21, 2020.
  * [LG14] François Le Gall.  Powers of tensors and fast matrix multiplication.  In Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation, ISSAC ’14, page 296–303, New York, NY, USA, 2014\. Association for Computing Machinery.
  * [Lov19] Shachar Lovett.  The analytic rank of tensors and its applications.  Discrete Analysis, 7:1–10, 2019.
  * [Nas20] Eric Naslund.  The partition rank of a tensor and k-right corners in fqn.  Journal of Combinatorial Theory, Series A, 174(105190), 2020.
  * [Pan80] V. Ya Pan.  New fast algorithms for matrix operations.  SIAM Journal on Computing, 9(2):321–342, 1980.
  * [Sto10] Andrew Stothers.  On the complexity of matrix multiplication.  PhD thesis, University of Edinburgh, 2010.
  * [Str69] Volker Strassen.  Gaussian elimination is not optimal.  Numerische mathematik, 13(4):354–356, 1969.
  * [Str86] Volker Strassen.  The asymptotic spectrum of tensors and the exponent of matrix multiplication.  In 27th Annual Symposium on Foundations of Computer Science (sfcs 1986), pages 49–54, 1986.
  * [Swe18] Joseph Swernofsky.  Tensor Rank is Hard to Approximate.  In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018), volume 116 of Leibniz International Proceedings in Informatics (LIPIcs), pages 26:1–26:9, Dagstuhl, Germany, 2018.
  * [Tao16] Terence Tao.  A symmetric formulation of the Croot-Lev-Pach-Ellenberg-Gijswijt capset bound.  https://terrytao.wordpress.com/2016/05/18/a-symmetric-formulation-of-the-croot-lev-pach-ellenberg-gijswijt-capset-bound/, May 2016.
  * [Wil12] Virginia Vassilevska Williams.  Multiplying matrices faster than coppersmith-winograd.  In Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing, STOC ’12, page 887–898, New York, NY, USA, 2012. Association for Computing Machinery.
  * [Win71] Shmuel Winograd.  On multiplication of $2\times 2$ matrices.  Linear Algebra and its Applications, 4(4):381–388, 1971.