# Matrix Multiplication and Number On the Forehead Communication

Josh Alman111Columbia University<EMAIL_ADDRESS>Jarosław
Błasiok222Columbia University<EMAIL_ADDRESS>
###### Abstract

Three-player Number On the Forehead communication may be thought of as a
three-player Number In the Hand promise model, in which each player is given
the inputs that are supposedly on the other two players’ heads, and promised
that they are consistent with the inputs of of the other players. The set of
all allowed inputs under this promise may be thought of as an order-3 tensor.
We surprisingly observe that this tensor is exactly the matrix multiplication
tensor, which is widely studied in the design of fast matrix multiplication
algorithms.

Using this connection, we prove a number of results about both Number On the
Forehead communication and matrix multiplication, each by using known results
or techniques about the other. For example, we show how the Laser method, a
key technique used to design the best matrix multiplication algorithms, can
also be used to design communication protocols for a variety of problems. We
also show how known lower bounds for Number On the Forehead communication can
be used to bound properties of the matrix multiplication tensor such as its
zeroing out subrank. Finally, we substantially generalize known methods based
on slice-rank for studying communication, and show how they directly relate to
the matrix multiplication exponent $\omega$.

##  1 Introduction

Number on the forehead (NOF) communication complexity was introduced by
Chandra, Furst and Lipton [CFL83] as a variant of Yao’s model of communication
complexity. Here, we consider $k$ players, each of them having one of $k$
inputs, but instead of providing the players with their inputs, we imagine
them having their inputs written on their foreheads — in particular each
player can observe all inputs _except_ for their own. Similar to the standard
communication complexity, the players wish to exchange as little communication
as possible, in order to jointly compute some function of their inputs.

As it turns out this innocuous alteration has deep mathematical consequences.
For example, being able to prove lower bounds for specific NOF problems with
$k=\Theta(\log^{c}n)$ players would imply explicit circuit complexity lower
bounds [HG90, BT94].

Moreover, even if we consider only three players, the theory of NOF
communication complexity is simultaneously extremely deep, and frustratingly
lacking. Its depth comes in part from a number of fascinating and perhaps
surprising connections between natural questions in NOF communication
complexity and well-studied problems in Ramsey Theory, extremal combinatorics
and additive combinatorics. For example, already in the seminal paper [CFL83],
a surprisingly efficient deterministic protocol was provided for the NOF
problem of checking whether $x+y+z=0$ in $\mathbb{Z}_{N}$, where
$x,y,z\in\mathbb{Z}_{N}$ are the inputs on the players’ foreheads (we will
call this problem $\textsc{Eval}_{\mathbb{Z}_{N}}$ from now on). The protocol
uses just $\mathcal{O}(\sqrt{\log N})$ communication, and makes use of
Behrand’s construction of a relatively dense set without three-terms
arithmetic progression [Beh46]. On the other hand, in the same paper they
showed an $\omega(1)$ lower bound for the $\textsc{Eval}_{\mathbb{Z}_{N}}$
problem using the Hales–Jewett theorem — a deep theorem in Ramsey theory.
Since then, connections with the Ruzsa–Szemerédi problem, Corner-Free Sets and
other objects from extremal combinatorics have been discovered, frequently
leading to state-of-the-art constructions [LPS19, AS20, AMS12, LS21, CFTZ22].

At the same time, perhaps because of these connections, many seemingly simple
questions about NOF communication complexity remain unresolved, despite the
fact that their number-in-hand variants are very easy to answer. For example,
completely resolving the communication complexity of
$\textsc{Eval}_{\mathbb{Z}_{N}}$ requires a significantly better understanding
of the correct quantitative dependency in the Roth’s theorem (that large
density subsets of $[N]$ contain a 3-terms arithmetic progression), and seems
to be far out of reach of current techniques.

Similarly, it is still open how to find an explicit $3$-party NOF problem
which can be solved with $\mathcal{O}(1)$ randomized communication complexity
(assuming shared randomness), but which requires $\Omega(n)$ deterministic
communication, even though this is a relatively simple property of Equality
for two-party communication, and even though, with a non-constructive
argument, it is possible to show that such NOF problems exist [DP08]. A
natural candidate for such a problem is checking whether $x+y+z=0$ in
$\mathbb{F}_{3}^{n}$ (or, more generally, if $xyz=1$ in a large power $G^{n}$
of some fixed group $G$, not necessarily abelian — we will call those problems
$\textsc{Eval}_{G^{n}}$), but proving a NOF communication complexity lower
bound has been so far elusive.

Problems like $\textsc{Eval}_{G^{n}}$, in which for any pair of inputs to two
of the players, there is exactly one input to the remaining player for which
they should accept, will be called _permutation problems_. These problems
always have $\mathcal{O}(1)$ randomized communication complexity, so they are
natural candidates to try to prove $\Omega(n)$ deterministic communication
lower bounds. Indeed, a number of recent works have studied permutation
problems toward this goal [BDPW10, CFTZ22].

The construction [CFL83] of an efficient protocol for
$\textsc{Eval}_{\mathbb{Z}_{N}}$ can be interpreted as a statement that
existence of a large set $S\subset G$ without three terms arithmetic
progressions in an abelian group $G$ can be used to provide an efficient
protocol for $\textsc{Eval}_{G}$; by contrapositive, a lower bound for the
communication complexity of $\textsc{Eval}_{G}$ would imply an upper bound for
the size of any such set $S$. This latter statement for the group
$\mathbb{F}_{3}^{n}$ used to be known as a _cap-set conjecture_ for few
decades, and has famously been positively resolved in 2016 [EG16, CLP17,
Tao16] — the largest set $S\subset\mathbb{F}_{3}^{n}$ without three terms
arithmetic progressions has size $\mathcal{O}(c^{n})$ for some $c<3$. This
leads to a natural question: can the techniques used to prove the cap-set
theorem be generalized to prove a linear lower bound for the communication
complexity of $\textsc{Eval}_{\mathbb{F}_{3}^{n}}$?

Christandl et al. [CFTZ22] recently identified a barrier against a direct
applications of such techniques — they used a method called _combinatorial
degenration_ to prove that a _subrank_ of a specific tensor associated with
the communication problem $\textsc{Eval}_{G^{n}}$ for an abelian group $G$ is
near-maximal — whereas an upper bound on this subrank would imply a desired
lower-bound for communication complexity.

###  1.1 Our contributions

In this paper, we study three-player communication through the lens of
_promise number-in-hand problems_. For an alphabet $\Sigma$, a promise problem
$(I,P)$ consists of two subsets $I\subset
P\subset\Sigma\times\Sigma\times\Sigma$. In this problem, the three players
are given as input $a,b,c\in\Sigma$, respectively, with the promise that
$(a,b,c)\in P$, and their goal is to determine whether $(a,b,c)\in I$. For
instance, usual number-in-hand communication corresponds to this model where
$P=\Sigma\times\Sigma\times\Sigma$.

NOF problems can also be viewed as promise number-in-hand problems. Each
player is given as an input a pair $(a_{i},b_{i})\in\Sigma^{2}$ for
$i\in\\{1,2,3\\}$, and their inputs are guaranteed to satisfy that
$a_{2}=b_{1},a_{3}=b_{2}$ and $a_{1}=b_{3}$. (For instance, one thinks of
$a_{2}$ and $b_{1}$ as the input on the head of player 3, so we are promised
that players 1 and 2 see the same value there.) Write
$P_{\textsc{nof}}\subset\Sigma^{2}\times\Sigma^{2}\times\Sigma^{2}$ to denote
the inputs that satisfy that promise.

A key idea we pursue is to interpret $I$ and $P$, not just as subsets of
inputs, but also as order-3 (3-dimensional) $\\{0,1\\}$-valued tensors. For
example, letting $N=|\Sigma|$, we can represent $P_{\textsc{nof}}$ as a
$\\{0,1\\}$-valued tensor $P_{\textsc{nof}}\in\mathbb{F}^{N^{2}\times
N^{2}\times N^{2}}$, with the tensor entry being one whenever the
corresponding tuple is a legal input.

As it turns out, $P_{\textsc{nof}}$ is _exactly_ the matrix multiplication
tensor, the same tensor which is extensively studied in the theory of fast
matrix multiplication algorithms! We leverage this extremely surprising, if
only formal connection, to transfer ideas which have been developed in
studying fast matrix multiplication to give new insights into NOF
communication complexity, and conversely, to use results proved originally
about NOF communication complexity and obtain new alternative proofs of
consequential properties of the matrix multiplication tensor.

We use this connection to prove the following results.

##### Communication Protocols from the Laser Method

We use the Laser method, the technique introduced by Strassen and used to
design the best-known matrix multiplication algorithms [Str86, CW87], as a
tool to design NOF communication protocols. For any three NOF problems
$I,J,K$, let $I\otimes J\otimes K$ (“their product”) denote the NOF problem of
solving the three simultaneously, i.e., given one input to each, determining
whether all three are accepting inputs. Using the Laser method, we show that
for any three permutation NOF problems $I,J,K$ with $n$-bit inputs, the
product $I\otimes J\otimes K$ (which has $3n$-bit inputs) can be solved using
only $n$ bits of communication deterministically.

For example, for any permutation NOF problem $I$ with $n$-bit inputs, one can
consider the problem of, given $N$ simultaneous inputs to $I$, determining if
they are all accepting inputs. A consequence of our protocol is that this can
be solved with $\frac{1}{3}nN+\mathcal{O}(n)$ bits of communication
deterministically. This implies constructions of surprisingly large corner-
free sets for powers of arbitrary abelian groups $G$.

By contrast, we show using a counting argument that a random NOF permutation
problem $I$ with $n$-bit inputs has requires deterministic communication
complexity $\geq n/3-\mathcal{O}(1)$. It was not previously clear to what
extent this is tight; our protocol shows that this bound can at least be
achieved for any permutation problem which is itself the product of three
permutation problems.

Our protocol should also be contrasted with the proof by probabilistic method
in [CFTZ22], which showed that every NOF permutation problem with $n$-bit
inputs has a protocol with communication complexity $n/2+\mathcal{O}(1)$,
improving in turn upon the trivial $n$ upper bound.

##### The Zeroing Out Subrank of Matrix Multiplication

A quantity which appears frequently in the theory of matrix multiplication
algorithms is the _zeroing out subrank_ of matrix multiplication, denoted
$Q_{zo}(\langle n,n,n\rangle)$. This is the size of the largest identity
tensor (3-dimensional analogue of the identity matrix) which can be achieved
as a zeroing out of the tensor $\langle n,n,n\rangle$ for multiplying two
$n\times n$ matrices. Strassen [Str86] famously proved that $Q_{zo}(\langle
n,n,n\rangle)\geq n^{2-o(1)}$, which is roughly as large as possible (since
$\langle n,n,n\rangle$ is an $n^{2}\times n^{2}\times n^{2}$ tensor), and used
it as part of the Laser method to design a faster algorithm for matrix
multiplication333See, e.g., [Blä13, Section 8]. Bounds used in algorithms are
sometimes described as bounds on a ‘monomial degeneration subrank’ or
‘combinatorial degeneration subrank’, but these are in turn ultimately used to
bound the zeroing out subrank via [Bin05]. Note that bounds on more general
notions like ‘border subrank’ or ‘subrank’ would not suffice in these
algorithms, since the subrank decomposition is applied only to the ‘outer
structure’ of a tensor in the Laser method [Str86].. Recent _barrier_ results
have also used this bound to rule out certain approaches to designing faster
matrix multiplication algorithms [AW21, Alm21, CVZ21].

In the bound $Q_{zo}(\langle n,n,n\rangle)\geq n^{2-o(1)}$, it is natural to
ask what is hidden by the $o(1)$. For instance, it was recently shown that the
‘border subrank’ of $\langle n,n,n\rangle$ is $\lceil\frac{3}{4}n^{2}\rceil$
[KMZ20]; is it possible that we also have $Q_{zo}(\langle
n,n,n\rangle)\geq\Omega(n^{2})$? This could improve low-order terms in some
applications.

In fact, we prove that this is not possible, and that $Q_{zo}(\langle
n,n,n\rangle)<n^{2}/\omega(1)$. To prove this, we build off of the work of
[LPS19], who showed a NOF communication lower bound, that any NOF permutation
problem requires $\omega(1)$ deterministic communication. Using our connection
between NOF communication and matrix multiplication, we are able to modify
their proof to get our upper bound on $Q_{zo}(\langle n,n,n\rangle)$.

Interestingly, the prior work [LPS19] proved their communication lower bound
using a connection with the Ruzsa–Szemerédi problem from extremal
combinatorics. Not only does our new proof show a connection between
$Q_{zo}(\langle n,n,n\rangle)$ and the Ruzsa–Szemerédi problem, but we are in
fact able to show that the two are _equivalent_! More precisely, it is
impossible to determine the precise asymptotics of $Q_{zo}(\langle
n,n,n\rangle)$ without also resolving the Ruzsa–Szemerédi problem. This is
interesting in contrast with the ‘border subrank’ which has been precisely
determined [KMZ20].

Finally, using the connection with NOF communication, we also provide an
alternative proof of Strassen’s lower bound $Q_{zo}(\langle n,n,n\rangle)\geq
n^{2-o(1)}$, deducing it as a corollary of the existence of the efficient
deterministic NOF protocol for $\textsc{Eval}_{\mathbb{Z}_{N}}$.

##### Slice-Rank Methods

Since their introduction [CFL83], NOF problems $I$ have been associated with a
corresponding 3-hypergraph $H$ whose chromatic number exactly characterizes
the deterministic communication complexity of $I$. One recent powerful
approach for bounding the chromatic number of such a hypergraph is the ‘slice
rank’ method, which was introduced to resolve the cap-set conjecture [CLP17,
EG16]. Roughly speaking, if one can show that the slice rank of the adjacency
tensor of $H$ is not too large, then this implies the chromatic number of $H$
is not too small, and hence a communication lower bound.

Since then, a few successful techniques have been introduced to bound the
slice ranks of many different tensors [Tao16, BCC+17]. Recent work [CFTZ21]
asked whether these techniques could give linear deterministic NOF
communication lower bounds. However, they showed that, unfortunately, it is
impossible to use such techniques to prove communication lower bounds for any
Eval group problem. They proved this by defining the corresponding adjacency
tensor and calculating that it has maximal ‘asymptotic subrank’ and hence
large slice rank.

We generalize their result and show that slice-rank methods cannot be used to
prove a linear deterministic communication lower bound for _any_ NOF
permutation problem (not just an Eval group problem). To show this, we observe
that for any NOF permutation problem, the corresponding adjacency tensor is
actually (a permutation of) the matrix multiplication tensor
$P_{\textsc{nof}}$. Since the matrix multiplication tensor is known to have
maximal asymptotic subrank [Str86], it follows that the adjacency tensor never
has small enough slice rank. In particular, this implies that in hindsight,
the tensor whose asymptotic subrank was computed in the prior work [CFTZ21] is
exactly the matrix multiplication tensor.

By contrast, we use slice-rank methods to prove linear lower bounds for other
promise problems. The key is that this method works whenever the _promise
tensor_ has low slice-rank. For example, consider the promise problem
$\textsc{Eq}_{\mathbb{F}_{3}^{N}}$, where parties receive inputs
$x,y,z\in\mathbb{F}_{3}^{N}$ with a promise that $x+y+z=0$, and they wish to
decide whether $x=y$. We prove that this problem requires $\Omega(N)$
communication. This may seem like it should be straightforward to prove (“how
could the third player’s input $z=-(x+y)$ possibly help the first two players
to test for equality?”), but we prove that the problem is actually
_equivalent_ to the cap-set problem (which was a long-open conjecture).

##### General Rank Methods and the Asymptotic Spectrum of Tensors

Slice-rank is one way to measure the ‘complexity’ of a tensor, but there are
many others, including other notions of tensor rank, and more generally a
spectrum of different measures which is well-studied in algebraic complexity
and tensor combinatorics called the ‘asymptotic spectrum of tensors’ [Str86,
WZ22]. Let $r$ be any of these measures (the reader may want to focus on the
case when $r$ is the tensor rank). We generalize the slice-rank method and
prove that for any promise problem $(I,P)$, its deterministic communication
complexity is at least $\log_{2}(r(I)/r(P))$. Hence, finding a measure $r$
which is larger for the problem $I$ than the promise $P$ leads to a
communication lower bound. (This is why, for slice rank, the fact that the
promise $P_{\textsc{nof}}$ has maximal slice rank means that a lower bound
cannot be proved in this way.)

This already has intriguing consequences when $r$ is tensor rank $R$.

For number-in-hand communication, we know that the promise tensor $P_{NIH}$ is
the all-1s tensor which has rank $R(P_{NIH})=1$. Hence, for any number-in-hand
problem $I$, we get a communication lower bound of $\log_{2}(R(I))$. This is
analogous to the standard upper bound in two-party deterministic communication
compleixty by the log of the rank of the communication matrix. Moreover, any
$2^{n}\times 2^{n}\times 2^{n}$ tensor $I$ (corresponding to an $n$-bit input
problem) which is not ‘degenerate’ in some way has rank at least $2^{n}$,
which explains why nearly all number-in-hand communication problems require
linear communication.

For NOF communication for $n$-bit inputs, as we’ve discussed, the promise
tensor $P_{NOF}$ is the matrix multiplication tensor. Determining the rank of
matrix multiplication is the _central question_ when designing matrix
multiplication algorithms; the matrix multiplication exponent $\omega$ is
defined exactly such that the rank of $P_{NOF}$ is
$R(P_{NOF})=(2^{n})^{\omega+o(1)}$. Hence, for any problem $I$ with rank
$R(I)\geq(2^{n})^{c}$, we get a communication lower bound of
$(c-\omega-o(1))\cdot n$. The fact that $\omega$ appears negated in this lower
bound is intriguing: this means that designing faster matrix multiplication
algorithms, and hence lowering the known upper bound on $\omega$, leads to an
improved communication lower bound for such problems $I$.

##### Matrix Multiplication as a Communication Problem

Finally, we consider how other promise problems can be used to shed further
light on NOF communication lower bounds. Let $I$ be any $n$-bit NOF problem,
let $N=2^{n}$, and let $T_{(\mathbb{Z}/N\mathbb{Z})^{2}}$ denote the structure
tensor of the group $(\mathbb{Z}/N\mathbb{Z})^{2}$, i.e., the tensor

$T_{(\mathbb{Z}/N\mathbb{Z})^{2}}=\sum_{a,b,c,d\in[N]}x_{(a,b)}y_{(c,d)}z_{(a+c\pmod{N},b+d\pmod{N})}.$

We observe that $P_{NOF}\subset T_{(\mathbb{Z}/N\mathbb{Z})^{2}}$ (after
appropriately permuting variables), and so it is well-defined to consider
three different promise problems using these three tensors: $(I,P_{NOF})$,
$(P_{NOF},T_{(\mathbb{Z}/N\mathbb{Z})^{2}})$, and
$(I,T_{(\mathbb{Z}/N\mathbb{Z})^{2}})$. Moreover, a simple triangle
inequality-style argument shows that their communication complexities are
related via:

$\mathcal{CC}(I,P_{NOF})\geq\mathcal{CC}(I,T_{(\mathbb{Z}/N\mathbb{Z})^{2}})-\mathcal{CC}(P_{NOF},T_{(\mathbb{Z}/N\mathbb{Z})^{2}}).$

On the left-hand side is exactly the deterministic NOF complexity of the
problem $I$ that we would like to prove a lower bound for. On the right-hand
side, $(I,T_{(\mathbb{Z}/N\mathbb{Z})^{2}})$ is a similar problem to the
original NOF problem of $I$, but with a weaker promise, and so it should be
easier to prove communication lower bounds for. What about
$\mathcal{CC}(P_{NOF},T_{(\mathbb{Z}/N\mathbb{Z})^{2}})$? (Recall that in this
problem, we’re given as input a term from the tensor
$T_{(\mathbb{Z}/N\mathbb{Z})^{2}}$, and our goal is to determine whether or
not it is a valid NOF input from $P_{NOF}$.)

For this problem, we give a protocol with communication $\leq n$ (the trivial
bound would be $2n$). Moreover, we prove a communication lower bound of
$\geq(\omega-2)n$ (this follows from the rank-based approach discussed above).
So, further improvements to the communication protocol actually _require_ fast
matrix multiplication (since they would imply an upper bound on $\omega$ via
this inequality). If it were the case that $\omega=2$ (which is popularly
conjectured), then it is plausible that this problem actually has sublinear
communication complexity. In that case, in order to prove a linear lower bound
for the NOF problem $(I,P_{NOF})$, it would suffice to prove a linear lower
bound for the seemingly-harder problem $(I,T_{(\mathbb{Z}/N\mathbb{Z})^{2}})$.
In summary, if we could design a faster matrix multiplication algorithm
achieving $\omega=2$, then this may be a promising approach to proving NOF
communication lower bounds.

##  2 Tensor Preliminaries

In this paper we will relate communication problems to related tensors and
their properties. We will focus on order-3 tensors (also known as
3-dimensional tensors). For a field $\mathbb{F}$ and three positive integers
$A,B,C$, we define $\mathbb{F}^{A\times B\times C}$ to be the set of tensors

$T=\sum_{a\in A}\sum_{b\in B}\sum_{c\in C}T_{a,b,c}x_{a}y_{b}z_{c}$

for coefficients $T_{a,b,c}\in\mathbb{F}$ (where $x_{a},y_{b},z_{c}$ are
formal variables). When the specific sets are not important, we will often
write $\mathbb{F}^{|A|\times|B|\times|C|}$ instead of $\mathbb{F}^{A\times
B\times C}$.

$T$ is $\\{0,1\\}$-valued if, for all $a,b,c$, we have
$T_{a,b,c}\in\\{0,1\\}$. Such tensors are in bijection with subsets of
$A\times B\times C$. All tensors considered in this paper are assumed to be
$\\{0,1\\}$-valued unless stated otherwise.

The field $\mathbb{F}$ that one works over will be primarily important to us
for the following definition. The (not necessarily $\\{0,1\\}$-valued) tensor
$T$ has rank 1 if it can be written as

$T=\left(\sum_{a\in A}\alpha_{a}x_{a}\right)\left(\sum_{b\in
B}\beta_{b}y_{b}\right)\left(\sum_{c\in C}\gamma_{c}z_{c}\right)$

for coefficients $\alpha_{a},\beta_{b},\gamma_{c}\in\mathbb{F}$. More
generally, the rank of the (not necessarily $\\{0,1\\}$-valued) tensor $T$,
denoted $R(T)$, is the minimum number of tensors of rank 1 which sum to $T$.

Rank is critical to the definition of the matrix multiplication exponent
$\omega$. For $n,m,p\in\mathbb{N}$, we write $\langle
n,m,p\rangle\in\mathbb{F}^{n^{2}\times n^{2}\times n^{2}}$ to denote the
matrix multiplication tensor

$\langle
n,m,p\rangle=\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{k=1}^{p}x_{i,j}y_{j,k}z_{k,i}.$

The exponent $\omega$ is defined as

$\omega:=\inf\\{t\mid R(\langle n,n,n\rangle)\leq n^{t}\text{ for some
}n\in\mathbb{N}\\}.$

Indeed, it is known that for any $\varepsilon>0$, matrix multiplication of
$n\times n$ matrices can be performed with an arithmetic circuit of size
$\mathcal{O}(n^{\omega+\varepsilon})$, and conversely, that any arithmetic
circuit for matrix multiplication can be converted into a tensor rank upper
bound which yields the same operation count in this way [Str73].

We say $T$ is an identity tensor if, for all $a\in A$, there is at most one
pair $(b,c)\in B\times C$ such that $T_{a,b,c}\neq 0$, and similarly for all
$b\in B$ and for all $c\in C$. Often, when $A=B=C$, one specifically thinks of
the identity tensor of size $k$ as a tensor $\sum_{a\in S}x_{a}y_{a}z_{a}$ for
some subsets $S\subset A$ of size $|S|=k$. To be clear that this is sufficient
but not necessary (as one could in general permute the indices), we will refer
to permutations of identity tensors.

If $T,T^{\prime}\in\mathbb{F}^{A\times B\times C}$, we say $T^{\prime}$ is a
zeroing out of $T$ if there are subsets $A^{\prime}\subset A,B^{\prime}\subset
B,C^{\prime}\subset C$ such that $T^{\prime}_{a,b,c}$ is equal to $T_{a,b,c}$
whenever $a\in A^{\prime},b\in B^{\prime},c\in C^{\prime}$, and
$T^{\prime}_{a,b,c}=0$ otherwise. In other words, we are setting coefficients
outside of $A^{\prime},B^{\prime},C^{\prime}$ to zero. We will sometimes write
$T^{\prime}=T|_{A^{\prime},B^{\prime},C^{\prime}}$.

The zeroing out subrank of $T$, denoted $Q_{zo}(T)$, is the maximum $k$ such
that $T$ has a zeroing out to a permutation of an identity tensor of size $k$.
This more combinatorial variant on the notion of ‘subrank’ (which uses
‘restrictions’ rather than zeroing outs) will be useful a number of times.

##  3 Promise problems and colored tensors

######  Definition 1.

A promise problem over alphabet $\Sigma$ is a pair of subsets $I\subset
P\subset\Sigma\times\Sigma\times\Sigma$, where $P$ is a set of allowed inputs
(the _promise_), and $I$ is the subset of accepting inputs (the _problem_).

To study those objects, we will introduce a notion of _colored tensors_. A
colored tensor is a pair $(I,T_{P})$, where
$T_{P}\in\mathbb{F}^{\Sigma\times\Sigma\times\Sigma}$ is a tensor and
$I\subset\mathrm{supp}(T_{P})$ is a subset of its non-zero terms. (We imagine
those terms to have a special color, and in what follows we will call them
_green_ terms). 3-party promise number in hand problems over the alphabet
$\Sigma$ are therefore in direct correspondence with $\\{0,1\\}$-valued
colored tensors over $\mathbb{F}^{\Sigma\times\Sigma\times\Sigma}$, where the
non-zero terms of the tensor $T$ corresponds to the set of allowed inputs, and
the subset $I$ of green terms corresponds to accepting inputs.

######  Definition 2.

For any field $\mathbb{F}$ we can define the _communication tensor_ of a
promise problem $(I,P)$ as a colored tensor $(I,T_{P})$, with
$T_{P}\in\mathbb{F}^{\Sigma\times\Sigma\times\Sigma}$ given by

$T_{P}:=\sum_{(i,j,k)\in P}x_{i}y_{j}z_{k}.$

We will say that $T_{P}$ is the _promise tensor_ of the problem $(I,P)$.

We will sometimes abuse notation, and use the same symbol to denote a
$\\{0,1\\}$-valued tensor $P\in\mathbb{F}^{A\times B\times C}$ and its support
$\mathrm{supp}(P)\subset A\times B\times C$ whenever it is clear from context.
All tensors we discuss in this paper are $\\{0,1\\}$-valued and for the vast
majority of the discussion the underlying field is irrelevant.

##### Communication Complexity Model

We use $\mathcal{CC}(I,P)$ to denote the deterministic communication
complexity of the promise problem $(I,P)$. To make this concrete, we consider
a shared blackboard model: here a protocol is given by a triple of functions,
one for each player, encoding what each player should append to the blackboard
in each round of communication, given the current state of the blackboard, and
their private input. Players write their communication on the blackboard in
cyclic order; in each stage each player can either append something to the
blackboard, accept the current instance, or reject the current instance. A
specific instance is accepted if _all players_ accept it (based on their own
input, and the final state of the blackboard). A protocol solves a promise
problem $(I,P)$ if it accepts all the inputs from $I$ and rejects all other
inputs from $P\setminus I$. (Since $P$ is the promise, the protocol need not
have any particular behavior on inputs outside of $P$.)

##### Asymptotic communication complexity

For a promise problem $(I,P)$ we use $(I,P)^{\otimes n}$ to denote a promise
problem in which parties are given $n$ valid instances of the original promise
problem $(I,P)$, and wish to determine whether _all_ of those instances
simultaneously are accepting.

More formally, $(I,P)^{\otimes n}$ is the promise problem with the promise
$P^{\otimes n}\subset(\Sigma^{n})\times(\Sigma^{n})\times(\Sigma^{n})$, i.e.,
for $A,B,C\in\Sigma^{n}$, the triple of sequences $(A,B,C)$ is in $P^{\otimes
n}$ if and only if we have $(A_{i},B_{i},C_{i})\in P$ for all $i\in[n]$. The
set of accepting instances $I^{\otimes n}$ is defined analogously. This
operation corresponds to the Kronecker product of the associated communication
tensors.

######  Definition 3.

For tensors $I^{(1)}\subset T^{(1)}\subset\mathbb{F}^{A_{1}\times B_{1}\times
C_{1}}$ and $I^{(2)}\subset T^{(2)}\subset\mathbb{F}^{A_{2}\times B_{2}\times
C_{2}}$ We define the Kronecker product of colored tensors
$(I^{(1)},T^{(1)})\otimes(I^{(2)},T^{(2)})$ as a colored tensor $(I,T)$ in
$\mathbb{F}^{A_{1}A_{2}\times B_{1}B_{2}\times C_{1}C_{1}}$, where
$T=T_{1}\otimes T_{2}$ satisfies

$T_{(a_{1},a_{2}),(b_{1},b_{2}),(c_{1},c_{2})}=T^{(1)}_{a_{1},b_{1},c_{1}}\cdot
T^{(2)}_{a_{2},b_{2},c_{2}},$

and $I=\\{(a_{1},a_{2}),(b_{1},b_{2}),(c_{1},c_{2}):(a_{i},b_{i},c_{i})\in
I_{i}\text{ for }i\in\\{1,2\\}\\}$.

We remark that all tensors considered in this work are order-3 tensors (also
known as 3-dimensional tensors), and we will use symbol $\otimes$ exclusively
to denote the Kronecker product of tensors (as opposed to tensor product).

We will define the asymptotic communication complexity of the problem $P$ as

$\underline{\mathcal{CC}}(I,P):=\lim_{n\to\infty}\frac{\mathcal{CC}((I,P)^{\otimes
n})}{n}.$

##### Permutation problems

We pay special attention to a particular class of communication problems,
which we will call _injection problems_ — as we will see later on, the
deterministic communication complexity of injection problems have very simple
combinatorial interpretation, and they all have protocols with constant
randomized communication (under public randomness).

######  Definition 4 (Injection problem).

Let $\pi_{1},\pi_{2},\pi_{3}:\Sigma^{3}\to\Sigma$ be projections onto first,
second, and third coordinate respectively.

We say that $(I,P)$ (where $I\subset P\subset\Sigma^{3}$) is an _injection
problem_ , if the tensor $T_{I}:=\sum_{(i,j,k)\in I}x_{i}y_{j}z_{k}$
restricted to the coordinates appearing in $I$ (i.e.
$(T_{I})|_{\pi_{1}(I),\pi_{2}(I),\pi_{3}(I)}$) is a permutation of an identity
tensor.

That is: for every valid input of the $i\in\Sigma$ of the first player, there
is at most one pair $j,k$, such that $(i,j,k)\in I$, and analogously for the
second and the third player.

######  Definition 5 (Permutation problem).

We say that $(I,P)$ is a permutation problem if $(I,P)$ is an injection
problem and moreover $|I|=\Sigma$.

Note that if $(I,P)$ is an injection (resp. permutation) problem, then
$(I,P)^{\otimes n}$ also is an injection (permutation) problem.

###  3.1 Number on the forehead problems as promise-number-in-hand problems

We can treat a NOF problem $I\subset\Sigma\times\Sigma\times\Sigma$ as a
promise problem over the alphabet $\Gamma:=\Sigma\times\Sigma$, where the
promise $P_{\textsc{nof}}\subset\Gamma^{3}$ is given by the following promise-
tensor

$P_{\textsc{nof}}:=\sum_{i,j,k\in\Sigma}x_{i,j}y_{j,k}z_{k,i}.$

A key observation that we will explore in this paper is that
$P_{\textsc{nof}}$ is exactly the matrix multiplication tensor $P=\langle
N,N,N\rangle$ where $N=|\Sigma|$.

The set of accepting instances $I\subset\Gamma\times\Gamma\times\Gamma$ can be
bijectively mapped into a subset $\tilde{I}\subset\langle N,N,N\rangle$ of
non-zero terms of the promise tensor, by
$\tilde{I}:=\\{((x,y),(y,z),(z,x)):(x,y,z)\in I\\}$.

Having interpreted number-on-the-forehead problems as number-in-hand problems
with promise $\langle N,N,N\rangle$, we observe that our more general
definition of the permutation problem agrees with the definition of the
permutation problem in [LPS19] for NOF problems — which are in turn are
equivalent to Latin squares of size $N\times N$.

An important family of examples of NOF permutation problems are Eval problems
induced by an abelian group $G$. Specifically, for any abelian group $G$, let
$\textsc{Eval}_{G}$ be the problem defined as follows. Players have $x,y,z\in
G$ on their foreheads, and they want to decide whether $x+y+z=0$. We can
represent the problem by its set of accepting instances $I\subset G^{3}$
defined by $I=\\{(x,y,z):x+y+z=0\\}$.

The observation that all NOF permutation problems admit an efficient
randomized protocol, generalizes to injection problems regardless of the
promise, using a constant communication randomized protocol for two-players
Equality problem.

######  Fact 6.

Every injection problem has a $O(1)$ randomized protocol with shared
randomness, regardless of the promise.

###### Proof.

First player, upon receiving his input $x$ can find unique $y_{1},z_{1}$, such
that $(x,y_{1},z_{1})\in I$. He can then proceed by using the randomized two-
player protocol for Equality to check whether $y_{1}=y$, and $z_{1}=z$, where
$y,z$ are inputs of the second and third player respectively. ∎

What can we say about the deterministic communication complexity of promise
injection problems? It turns out that we can express it equivalently as a
question about the smallest proper coloring of the communication tensor
$(I,P)$.

######  Definition 7.

Consider a colored tensor $T=(I,P)$, We say that a subset of its green terms
$S\subset I$ is an independent set if $S$ is a permutation of an identity
tensor and the restriction $T|_{\pi_{1}(S),\pi_{2}(S),\pi_{3}(S)}$ is equal to
$S$. We use $\alpha(T)$ to denote the size of largest independent set in the
colored tensor $T$.

If $T$ is an ordinary tensor, we use $\alpha(T)$ to denote the size of the
largest independent set in the colored tensor $(\mathrm{supp}(T),T)$ (i.e., we
treat all its terms as green). This coincides with the usual notion of zero-
out subrank of a tensor.

Note that if $T=(I,P)$ is an injection problem, $S\subset I$ is an independent
set if and only if all non-zero terms in the restriction
$T|_{\pi_{1}(S),\pi_{2}(S),\pi_{3}(S)}$ are in $I$ — that is, if we denote by
$S_{i}:=\pi_{i}(S)$ then set $S$ is independent if and only if

$\mathrm{supp}(T)\cap(\pi_{1}(S_{1})^{-1}\times\pi_{2}(S_{2})^{-1}\times\pi_{3}(S_{3})^{-1})=S.$

With a definition of an independent set, we can define a proper coloring and
the chromatic number of a colored tensor in a natural way.

######  Definition 8.

For a colored tensor $T:=(I,P)$ we say that $\tau:I\to[k]$ is a proper
coloring if for all colors $c\in[k]$, the set $\tau^{-1}(c)$ is independent.

We denote by $\chi(T)$ the _chromatic number_ of tensor $T$ — the smallest
$k$, such that there is a proper coloring $\tau:I\to[k]$. Again, if $T$ is an
ordinary tensor, we use a shorthand $\chi(T):=\chi(\mathrm{supp}(T),T)$.

The proof of the following characterization follows exactly the original proof
in [CFL83], just phrased in a slightly more general language of promise
problems instead of specifically Number on the Forehead problems.

######  Theorem 9.

The deterministic communication complexity of any promise injection problem
$(I,P)$ is equal to $\lceil\log\chi(I,P)\rceil$.

###### Proof.

Given a coloring $\tau:I\to[k]$, we will describe a communication protocol
with complexity $\lceil\log k\rceil$. The first player, with an input $x$,
looks at the only $y^{(1)},z^{(1)}$, s.t. $(x,y^{(1)},z^{(1)})\in I$, and
writes down the color $\tau(x,y^{(1)},z^{(1)})$. Similarly, the second player,
with an input $y$, compares the written color with the color of
$(x^{(2)},y,z^{(2)})\in I$, and analogously the third player. Clearly, if
$(x,y,z)$ was an accepting instance, all three of the triples in the
consideration would be the same
($x^{(2)}=x^{(3)}=x,y^{(1)}=y^{(3)}=y,z^{(1)}=z^{(2)}=z$), and therefore the
colors under consideration would agree — the protocol will correctly accept
such an instance.

On the other hand, if all
$(x,y^{(1)},z^{(1)}),(x^{(2)},y,z^{(2)}),(x^{(3)},y^{(3)},z)$ have the same
color $c$, let us take the independent set $S:=\tau^{-1}(c)\subset I$, then
$x\in\pi_{1}(S),y\in\pi_{2}(S),z\in\pi_{3}(S)$, and since $(x,y,z)\in P$ and
$S$ is an independent set, we must have $(x,y,z)\in I$ — i.e. the instance was
accepting. This completes the proof that a coloring $\tau:I\to[k]$ implies
existence of an efficient protocol.

The converse is similar: given a protocol for a problem $(I,P)$ with
communication at most $k$, we can use the transcript of the communication on
each input $(x,y,z)\in I$ as a color for the term. This yields a mapping
$\tau:I\to[2^{k}]$, and all we need to check is that it is a proper coloring.
Indeed, let us chose an arbitrary color $c$, and take a set $S=\tau^{-1}(c)$.
If there was $(x,y,z)\in P-I$, such that
$(x,y,z)\in\pi_{1}(S)\times\pi_{2}(S)\times\pi_{3}(S)$, the communication
transcript on the (allowed) input $(x,y,z)$ would have been the same as on
accepting inputs
$(x,y^{(1)},z^{(1)}),(x^{(2)},y,z^{(2)}),(x^{(3)},y^{(3)},z)$, and therefore
each player would have accepted it — contradicting correctness of the
protocol, since $(x,y,z)\not\in I$. ∎

###  3.2 Comparison with standard bounds for the NOF communication complexity

What we discussed so far is a slightly different perspective on the standard
way of characterizing NOF communication complexity (already present in
[CFL83]). Classically, with NOF permutation problem
$I\subset\Gamma\times\Gamma\times\Gamma$, one associated a directed
3-hypergraph $H$, and the logarithm of the chromatic number of this hypergraph
is equal to the deterministic communication complexity of the associated
problem.

We will show that in fact the adjacency tensor of the aforementioned
hypergraph $H$ is just a permutation of the promise tensor $P_{\textsc{nof}}$
(i.e., the matrix multiplication tensor), and the permutation is uniquely
determined by the problem $I$ — it corresponds to permuting variables $y_{i}$
and $z_{i}$ in a way such that $I$ is exactly on the diagonal of the tensor.

This provides a generalization, and another perspective on the barrier against
using a slice-rank or any other bounds on the subrank of the adjacency tensor
of $H$ as a way to show a lower bound for communication complexity of $H$.

Specifically, note that any independent set $S\subset V(H)$ induces a zeroing-
out of the adjacency tensor of the hypergraph $H$ to a large identity
subtensor (given by restriction to indices in $S\times S\times S$ — note that
in the construction of the hypergraph $H$ and its adjacency tensor, we include
self-loops $(t,t,t)$ for each $t\in V(H)$). One could then hope to show a
lower bound on the chromatic number of the hypergraph $H$ by upper bounding
the size of the largest independent set, which in turn can be upper bounded by
subrank of adjacency sub-tensor. Finally, it is known that subrank of any
tensor is always bounded by its slice-rank, and a few successful techniques
for controlling slice-ranks of particular tensors of interest have been
developed [Tao16, BCC+17].

This, apparently promising avenue for showing lower bounds for specific NOF
permutation problems unfortunately has to fail. In [CFTZ22] it was shown that
similar techniques as those used by Strassen to prove lower bound on the
asymptotic subrank of the matrix multiplication tensor, can be used to lower
bound the asymptotic subrank of the adjacency tensor for any Eval group
problem — it is maximally large. We observe that this is not a coincidence: in
fact all adjacency tensors constructed this way are just permutations of the
matrix-multiplication tensor, so the lower bound for asymptotic subrank of the
matrix multiplication tensor directly applies — not only for problems arising
as $\textsc{Eval}_{G}$, but more generally for all number-on-the-forehead
permutation problems.

######  Definition 10 (Communication Hypergraph [CFL83]).

For a permutation NOF problem $I\subset\Gamma\times\Gamma\times\Gamma$, we
define its communication hypergraph $H(I)$ to be an order-3 hypergraph, with
vertices $V(H(I))=I$ — set of all accepting instances, and hyperedges
constructed in the following way: for all
$(x,y,z)\in\Gamma\times\Gamma\times\Gamma$, let $T_{1}:=(x,y,z^{\prime})\in I$
be the only triple in $I$ with agreeing with $(x,y,z)$ in the first two
coordinates, and similarly $T_{2}:=(x^{\prime},y,z)\in
I,T_{3}:=(x,y^{\prime},z)\in I$.

Then $E(H(I))=\\{(T_{1},T_{2},T_{3}):(x,y,z)\in\Gamma^{3}\\}$.

######  Fact 11.

The adjacency tensor of the hypergraph $H(I)$ is a permutation of the matrix
multiplication tensor $\langle|\Gamma|,|\Gamma|,|\Gamma|\rangle$.

Moreover if we consider a set of green terms
$\tilde{I}\subset\langle|\Gamma|,|\Gamma|,|\Gamma|\rangle$ given by
$\tilde{I}=\\{((x,y),(y,z),(z,x)):(x,y,z)\in I\\}$ in the colored
communication tensor for the problem $I$, this set corresponds under the
aforementioned permutation exactly to the set of diagonal terms
$\\{(t,t,t):t\in I\\}$ of the adjacency tensor of $H(I)$.

###### Proof.

Consider a map $\pi_{12}:I\to\Gamma\times\Gamma$, given by
$\pi_{12}(x,y,z)=(x,y)$, and similarly $\pi_{23},\pi_{13}$. Note that those
three bijections between $I$ and $\Gamma\times\Gamma$. Applying those
bijections to three axes of the adjacency tensor $A$ of the hypergraph $H(I)$,
we see that an image of any hyperedge $(T_{1},T_{2},T_{3})$ is in the
Definition 10 is
$(\pi_{12}(T_{1}),\pi_{23}(T_{2}),\pi_{13}(T_{3}))=((x,y),(y,z),(x,z))$ — a
non-zero term of the matrix multiplication tensor
$\langle|\Gamma|,|\Gamma|,|\Gamma|\rangle$. All the non-zero terms of the
matrix multiplication tensor can be obtained this way: since, by construction
of the communication hypergraph, any term $((x,y),(y,z),(x,z))$ can be lifted
to an hyperedge $(T_{1},T_{2},T_{3})\in H(I).$

Finally, the statement about the image of the diagonal follows directly from
the definition of permutations $\pi_{12},\pi_{23}$ and $\pi_{13}$ and
construction of the hypergraph $H$. ∎

######  Corollary 12.

For any NOF permutation problem, the adjacency tensor of its communication
hypergraph has maximal asymptotic subrank.

###  3.3 Lower bounding the communication complexity of random NOF permutation
problem

In this section we will show that a random NOF permutation problem over the
alphabet $[N]\times[N]\times[N]$, where $N=2^{n}$ requires $\geq
n/3-\mathcal{O}(1)$ deterministic communication. This is a simple counting
argument, similar in spirit to the one used in [DP08]. Since the NOF
permutation problems over $[N]\times[N]\times[N]$ are bijective with Latin
squares of size $N\times N$, known upper and lower bounds for the number of
Latin squares can be used in our proof.

The following is a consequence of the fact that any Latin square can be
constructed by repeatedly taking a perfect matching in a regular bipartite
graph, and using standard bounds on the number of perfect matchings in a
$k$-regular bipartite graph.

######  Theorem 13 ([VLW01]).

Total number $\\#P$ of NOF permutation problems over $[N]\times[N]\times[N]$
satisfies

$N^{N^{2}}e^{-N^{2}}\leq\\#P\leq N^{N^{2}}.$

With this in hand, we can prove

######  Theorem 14.

For most of NOF permutation problems $(I,P)$, over the alphabet $[N]$ where
$N=2^{n}$, we have $\mathcal{CC}(I,P)\geq\frac{n}{3}-\mathcal{O}(1)$.

###### Proof.

Let $(I,P)$ be a NOF permutation problem over $[N]\times[N]\times[N]$ with
communication complexity $d$. By Theorem 9 communication complexity is
equivalent to the existence of proper coloring $\kappa:I\to\\{0,1\\}^{d}$.
Since $I$ is a permutation problem, for any $x\in[N]\times[N]$, there is a
unique $\pi_{1}^{-1}(x)\in I\subset([N]\times[N])^{3}$ (where
$\pi_{1}:([N]\times[N])^{3}\to[N]\times[N]$ is the projection onto first
coordinate). We can define $\kappa_{1}:[N]\times[N]\to\\{0,1\\}^{d}$ as
$\kappa_{1}(x):=\kappa(\pi_{1}^{-1}(x))$. Analogously, we define $\kappa_{2}$
and $\kappa_{3}$.

We observe that the triple of functions $(\kappa_{1},\kappa_{2},\kappa_{3})$
uniquely determines $I$. Indeed, for $(a,b,c)\in P$ to check if $(a,b,c)\in
I\iff\kappa_{1}(a)=\kappa_{2}(b)=\kappa_{3}(c)$. Therefore, the number of bits
to specify a problem with communication complexity $d$ (i.e. the logarithm of
the number of such problems) is at most $3dN^{2}$ — to specify a function
$\kappa:[N]\times[N]\to\\{0,1\\}^{d}$ we need $dN^{2}$ bits.

On the other hand, using the lower bound of Theorem 13, we need $N^{2}\log
N-\mathcal{O}(N^{2})$ bits to write down arbitrary NOF permutation problem.
Therefore if $d\leq(\log N)/3-\mathcal{O}(1)$, most of the problems do not
have a protocol with communication complexity $d$. ∎

###  3.4 Background on independence number and coloring of matrix
multiplication tensor

The following statement asserting that matrix-multiplication tensor has almost
maximal zero-out subrank is an important insight in the study of matrix
multiplication. It has been originally proven by Strassen in [Str87], and has
been used as a technical step in the design of some of the fast matrix
multiplication algorithms. Here we will use it as a tool in the proof of
Theorem 20. On the other hand, in Section 3.6 we will discuss how, using our
connection between number on the foreheads protocol and structural properties
of the matrix multiplication tensor, the following statement can be easily
deduced from the known results in the NOF communication complexity on
efficient protocols for some permutation problems.

######  Theorem 15 ([Str87]).

There is $I\subset\mathrm{supp}{\langle N,N,N\rangle}$, such that $|I|\geq
N^{2-o(1)}$, and the restriction $\langle
N,N,N\rangle|_{\pi_{1}(I),\pi_{2}(I),\pi_{3}(I)}$ is a permutation of the
identity tensor, i.e. $Q_{zo}(\langle N,N,N\rangle)\geq N^{2-o(1)}$.

Equivalently, in the notation introduced in this work,

$\alpha(\langle N,N,N\rangle)\geq N^{2-o(1)}.$

The following is a standard technique of lifting the large independent set to
a small coloring in symmetric combinatorial objects. We include the proof for
completeness.

######  Definition 16 (Automorphism group).

For a colored tensor $T=(I,P)$, we define $\mathrm{Aut}(T)$ to be the set of
all triples of permutations $(\sigma_{1},\sigma_{2},\sigma_{3})$ such that
$\sigma(I)=I$, and moreover for all $(x,y,z)$ we have
$T_{x,y,z}=T_{\sigma_{1}(x),\sigma_{2}(y),\sigma_{3}(z)}$.

######  Lemma 17.

For a colored tensor $T=(I,P)$ if for any two green elements $a,b\in I$, there
is a $\sigma\in\mathrm{Aut}(T)$, s.t. $\sigma(a)=b$, then

$\chi(T)\leq\frac{|I|}{\alpha(T)}\log|I|.$

###### Proof.

Let $S\subset I$ be an independent set, and $\sigma\sim\mathrm{Aut}(T)$ a
uniformly random element of the automorphism group. Then clearly $\sigma(S)$
is also an independent set. We claim that for any $x\in I$, we have
$\Pr(x\in\sigma(S))=\frac{|S|}{|I|}$. Indeed, let $S=\\{s_{1},s_{2},\ldots
s_{m}\\}$. The subset $T\subset\mathrm{Aut}(T)$ of permutations $\sigma$ such
that $\sigma(s_{1})=x$ is exactly a coset of a subgroup $H$ in
$\mathrm{Aut}(T)$ where $H$ is a set of permutations fixing $x$, i.e.
$H=\\{\sigma:\sigma\in\mathrm{Aut}(T),\sigma(x)=x\\}$. Number of such cosets
is exactly $|I|$, since we assumed that $x$ can be mapped to any other $s\in
I$ by some permutation in $\mathrm{Aut}(T)$ (and no other element, by the
property of automorphism group that each $\sigma\in\mathrm{Aut}(T)$ preserves
green terms: $\sigma(I)=I$). Since all cosets of a given subgroup are disjoint
and have the same size, we get $\Pr(\sigma(s_{1})=x)=1/|I|)$. Therefore

$\Pr(x\in\sigma(S))=\sum_{i\leq|S|}\Pr(x=\sigma(s_{i}))=|S|/|I|.$

Finally, if we consider $K=C(|I|\log|S|)/|S|$ independent random permutations
$\sigma_{1},\sigma_{2},\ldots,\sigma_{m}\in\mathrm{Aut}(T)$, we wish to say
that with positive probability for every element $x\in I$ it is covered by at
least one set $\sigma_{i}(S)$. Indeed, in expectations, each of those is
covered by $C\log|S|$ such sets, and applying a standard Chernoff and union
bound argument, we reach the conclusion.

Having a covering of $I$ by $K$ independents sets, we can easily find a
coloring $\tau:I\to[K]$ mapping an elemnet $x\in I$ to the smallest $i\in[K]$
such that $x\in\sigma_{i}(S)$. ∎

######  Corollary 18.

The chromatic number of the matrix multiplication tensor satisfies

$\chi(\langle N,N,N\rangle)\leq N^{1+o(1)}.$

We shall also need the following standard fact on the Kronecker products of
matrix multiplication tensors.

######  Fact 19 (see, e.g., [Blä13, Page 24]).

The Krnoecker product of matrix multiplication tensors satisfies

$\langle N_{1},M_{1},P_{1}\rangle\otimes\langle
N_{2},M_{2},P_{2}\rangle=\langle N_{1}N_{2},M_{1}M_{2},P_{1}P_{1}\rangle$

###  3.5 Laser method gives a non-trivial asymptotic protocol for all NOF
permutation problems

In this section we will use the celebrated Laser method, introduced to design
fast matrix multiplication algorithms [Str86, CW87], to prove the following
surprising upper bound on the asymptotic NOF communication complexity of the
third player of arbitrary permutation problem.

######  Theorem 20.

For every triple of NOF permutation problems $I,J,K$, each over
$\\{0,1\\}^{n}\times\\{0,1\\}^{n}\times\\{0,1\\}^{n}$, we have

$\mathcal{CC}(I\otimes J\otimes K)\leq(1+o(1))n.$

(Note that the trivial bound is $\mathcal{CC}(I\otimes J\otimes K)\leq 3n$.)

In particular for any NOF permutation problem $P$ over
$\\{0,1\\}^{n}\times\\{0,1\\}^{n}\times\\{0,1\\}^{n}$, we have

$\underline{\mathcal{CC}}(P)\leq(1+o(1))\frac{n}{3}.$

We define the _block colored tensor_ to be a colored tensor $(I,T)$ over
$A\times B\times C$ together with a collection of partitions
$A=A_{1}\cup\ldots A_{p}$, $B=B_{1}\cup\ldots\cup B_{q}$, and
$C=C_{1}\cup\ldots C_{q}$.

The _outer structure_ of a block tensor $T$, is a tensor $\mathrm{Out}(T)$
over $[p]\times[q]\times[r]$ with $\mathrm{Out}(T)_{i,j,k}=1$ if and only if
the restriction $T|_{A_{i},B_{j},C_{k}}\not=0$ (and
$\mathrm{Out}(T)_{i,j,k}=0$ otherwise). The _inner structure_ $\mathcal{I}(T)$
of a block tensor $T$ is a collection of (colored) tensors
$T|_{A_{i},B_{j},C_{k}}$. The notions of outer and inner structure feature
prominently in the Laser method; see e.g., [Blä13, Section 8].

######  Lemma 21.

For a block-colored tensor $T$, we have

$\chi(T)\leq\chi(\mathrm{Out}(T))\cdot\max_{T^{\prime}\in\mathcal{I}(T)}\chi(T^{\prime}).$

###### Proof.

This is immediate — to find a proper coloring for the set of green terms $I$
of a block tensor $T$, we can map an element $x\in I$ to $(c_{1},c_{2})$,
where $c_{1}$ is a color assigned to the block in which $x$ lies in the
coloring of $\mathrm{Out}(T)$, and $c_{2}$ is a color assigned to $x$ in the
coloring of the block itself.

We need to show that each color class is an independent set. With an induced
partition of $A,B,C$, this amounts to observing that for any block tensor for
which $\mathrm{Out}(T)$ is is a permutation of the identity tensor, as well as
all tensors in $\mathcal{I}(T)$, the entire tensor also is a permutation of
the identity tensor. ∎

######  Fact 22.

Let $T^{1},T^{2}$ be a pair of block-colored tensor. Then $T:=T^{1}\otimes
T^{2}$ is a block colored tensor, with the outer structure
$\mathrm{Out}(T)=\mathrm{Out}(T^{1})\otimes\mathrm{Out}(T^{2})$, and the inner
structure $\mathcal{I}(T)\subset\mathcal{I}(T^{1})\otimes\mathcal{I}(T^{2})$
(Here, for two collections of tensors $\mathcal{A}$ and $\mathcal{B}$ we use
$\mathcal{A}\otimes\mathcal{B}:=\\{a\otimes
b:a\in\mathcal{A},b\in\mathcal{B}\\}$.)

###### Proof.

Directly follows from the definition. ∎

######  Fact 23.

For any pair of colored tensors $T_{1},T_{2}$, we have $\chi(T_{1}\otimes
T_{2})\leq\chi(T_{1})\chi(T_{2})$.

###### Proof.

Given two colorings $\kappa_{1}:I_{1}\to[k_{1}]$ and
$\kappa_{2}:I_{2}\to[k_{2}]$ we can construct a coloring of the Kronecker
product $T_{1}\otimes T_{2}$ using pairs $[k_{1}]\times[k_{2}]$, by mapping a
term $((i_{1},i_{2}),(j_{1},j_{2}),(k_{1},k_{2}))\in I_{1}\otimes I_{2}$ to a
pair $(\kappa_{1}(i_{1},j_{1},k_{1}),\kappa_{2}(i_{2},j_{2},k_{2}))$. The fact
that it is a proper coloring follows directly from the fact that Kronecker
product of two identity tensors is again an identity tensor. ∎

######  Lemma 24.

There is a triple of partitions $\mathcal{A},\mathcal{B},\mathcal{C}$ such
that for any NOF permutation-problem $(I,P_{\textsc{nof}})$, the block-colored
tensor $T:=(I,P_{\textsc{nof}},\mathcal{A},\mathcal{B},\mathcal{C})$ induced
by those partitions satisfies the following conditions

  * •

The outer structure $\mathrm{Out}(T)=\langle N,1,1\rangle$.

  * •

Every colored tensor in the inner structure $(Y,T^{\prime})\in\mathcal{I}(T)$
has $T^{\prime}=\langle 1,N,N\rangle$ and $\chi(Y,T^{\prime})=1$.

###### Proof.

Consider partitions $\mathcal{A}:=(A_{1},\ldots,A_{n})$ where
$A_{t}:=\\{(i,t):i\in[N]\\}$, similarly $\mathcal{B}:=(B_{1},\ldots B_{N})$
where $B_{t}=\\{(t,i):i\in[N]\\}$, and finally
$\mathcal{C}:=(C):=([N]\times[N])$ is a trivial partition with a single part.

First note that with this partition of the matrix multiplication tensor $P$,
the block $A_{t_{1}}\times B_{t_{2}}\times C$ is non-empty if and only if
$t_{1}=t_{2}$,

$\mathrm{Out}(T)=\sum_{t}x_{1,t}y_{t,1}z_{1,1},$

is the matrix multiplication tensor $\langle N,1,1\rangle$.

Moreover, let us consider an arbitrary non-empty block $A_{t}\times
B_{t}\times C$. Tensor $T$ restricted to this block is

$T|_{A_{t}\times B_{t}\times C}=\sum_{j,k}x_{j,t}y_{t,k}z_{k,j},$

which is exactly a $\langle 1,N,N\rangle$ matrix multiplication tensor.

Note now that the projection $\pi_{3}:A_{t}\times B_{t}\times C\to C$ induces
a bijection between $C$ and $Y:=\mathrm{supp}(T|_{A_{t}\times B_{t}\times
C})$. If we look at $S:=I\cap Y$, we wish to argue that $S$ is an independent
set in $T|_{A_{t}\times B_{t}\times C}$. Indeed, denoting $S_{i}:=\pi_{i}(S)$,
since $(I,P_{\textsc{nof}})$ is a permutation problem, all we need to argue is
that

$\pi_{1}^{-1}(S_{1})\times\pi_{2}^{-1}(S_{2})\times\pi_{3}^{-1}(S_{3})\cap
Y=S.$

But since $\pi_{3}$ is bijection, we already have $(A_{t}\times
B_{t}\times\pi_{3}^{-1}(S_{3}))\cap Y=S$. ∎

We are now ready to prove Theorem 20.

###### Proof of Theorem 20.

For permutation NOF problems $I,J,K$, according to Lemma 24 we can chose a
block-colored tensor structure $T_{I},T_{J},T_{K}$, such that
$\mathrm{Out}(T_{I})=\langle N,1,1\rangle$, $\mathrm{Out}(T_{J})=\langle
1,N,1\rangle$ and $\mathrm{Out}(T_{K})=\langle 1,1,N\rangle$.

By 22 and 19, the block-colored tensor $T=T_{I}\otimes T_{J}\otimes T_{K}$
satisfies $\mathrm{Out}(T)=\langle N,N,N\rangle$, and by 23 every colored
tensor $Z\in\mathcal{I}(T)$ has $\chi(Z)=1$ (since it is a product of three
colored tensors with chromatic number $1$).

By Corollary 18, $\chi(\langle N,N,N\rangle)\leq N^{1+o(1)}$, and finally
using Lemma 21,

$\chi(T)\leq\chi(\mathrm{Out}(T))\max_{T^{\prime}\in\mathcal{I}(T)}\chi(T^{\prime})\leq
N^{1+o(1)}.$

The communication complexity bound now follows from the characterization in
Theorem 9. ∎

###  3.6 Zeroing out subrank of the matrix multiplication tensor

We will use the connection between number on the forehead communication
complexity, and structural properties of matrix multiplication tensor to find
a non-trivial _upper bound_ for the zero-out subrank of matrix multiplication
tensor — i.e., an upper bound on the size of the largest diagonal subtensor to
which matrix multiplication tensor can be zeroed-out.

Authors of the work [LPS19] observed a connection between the NOF
communication complexity and the Ruzsa–Szemerédi problem. In particular, they
proved a super-constant lower bound for NOF communication complexity of _any_
permutation problem, as a corollary of the Ruzsa–Szemerédi theorem (which in
turns is proved via the triangle-removal lemma).

Here, we observe that with our connection between NOF communication and the
matrix-multiplication tensor, we can use their proof to show a somewhat
stronger statement — the upper bound on the zero-out subrank of matrix
multiplication.

######  Theorem 25.

The zero-out subrank of matrix multiplication satisfies

$Q_{zo}(\langle N,N,N\rangle))\leq N^{2}/2^{c\log^{*}N}.$

Note that this theorem (together with Proposition 27) implies in fact the
$\Omega(\log^{*}N)$ lower bound for all NOF permutation problems present in
[LPS19], and the proof is almost identical.

Before we continue, we shall state a convenient well-known equivalent
formulation of the Ruzsa–Szemerédi theorem. The sub-quadratic upper bound of
the quantity below has been famously proven by Ruzsa and Szemerédi in 1978
[RS78], using the notorious triangle removel lemma (in fact they considered a
slightly different formulation, the $(6,3)$-problem, but it can be easily seen
to be equivalent to the following statement [CEMS91]). Substituting a
quantitative version of the triangle removal lemma by Fox [Fox11] in their
proof leads to the following quantitative bound.

######  Theorem 26 ([RS78, CEMS91, Fox11]).

For any graph $G(V,E)$, let $\mathcal{C}$ be a collection of all triangles in
the graph $G$. If all those triangles are edge-disjoint, then
$|\mathcal{C}|\leq N^{2}/2^{c\log^{*}N}$ where $N=|V|$.

With this theorem in hand, it is easy to show a sub-quadratic upper bound on
the largest independent set in the matrix multiplication tensor. In fact the
quantitative question about the density of the largest independent set in the
matrix multiplication tensor is equivalent to the Ruzsa–Szemerédi problem.

###### Proof of Theorem 25.

Consider an independent set $\tilde{S}\subset\langle N,N,N\rangle$ — we can
treat it as a subset $S\subset[N]\times[N]\times[N]$. Let us now consider the
following tri-partite graph on $[N]\times[3]$: for each $(a,b,c)\in S$ we put
a triangle on vertices $(a,0),(b,1)$ and $(c,2)$. This construction yields a
graph $G$ on $3N$ vertices, together with a collection $\mathcal{C}$ of its
$|S|$ triangles. To appeal to the Theorem 26, we need to show that triangles
in the collection $\mathcal{C}$ are edge-disjoint, and that those are all the
triangles in a graph $G$.

First of all, those are edge disjoint — if we had a pair of distinct triangles
in $\mathcal{C}$ sharing an edge, it would correspond to two elements
$(a,b,c_{1})\in S$ and $(a,b,c_{2})\in S$ — a contradiction with an assumption
that $S$ is an independent set in matrix multiplication tensor.

Similarly, since the graph $G$ is tri-partite, the only possible triangle are
of form $(a,0),(b,1),(c,2)$ for some $a,b,c$. We wish to show that if $S$ was
an independent set, this is possible only for
$(a^{\prime},b^{\prime},c^{\prime})\in S$.

Indeed, if the edge $(a,0),(b,1)$ was included in the graph, there must have
been a tuple $(a,b,c^{\prime})\in S$, and analogously $(a,b^{\prime},c)\in
S,(a^{\prime},b,c)\in S$ for some $a^{\prime},b^{\prime},c^{\prime}$. Since
$S$ was an independent set, this readily implies that
$a^{\prime}=a,b^{\prime}=b,c^{\prime}=c$ and indeed $(a,b,c)\in S$. ∎

####  3.6.1 Lower bound for matrix multiplication subrank from NOF protocols

In the study of the matrix multiplication tensor, lower bounds on its zero-out
subrank are much more consequential than upper bounds. Strassen proved that
$\alpha(\langle N,N,N\rangle)\geq N^{2-o(1)}$, which is almost maximal (since
the tensor $\langle N,N,N\rangle$ has size $N^{2}\times N^{2}\times N^{2}$,
the largest diagonal tensor one could potentially hope to find there is of
size $N^{2}$). He used this together with the Laser method to design a fast
matrix multiplication algorithm in [Str86], and all subsequent record-holding
matrix multiplication algorithms have also used this. At the same time, recent
barrier results [AW21, Alm21, CVZ21] used the lower bounds on the subrank of
matrix multiplication to prove barrier against certain approaches for proving
that the matrix multiplication constant $\omega=2$. (Roughly speaking, using
our notation here, they show that since $\alpha(\langle N,N,N\rangle)$ is so
large, one would need to use an intermediate tensor $T$ with $\alpha(T)$ also
large in order to design a sufficiently fast algorithm.)

One of the crucial ingredients in the proof using the Laser method that
$\alpha(\langle N,N,N\rangle)\geq N^{2-o(1)}$ is leveraging the existence of a
subset $S\subset[N]$ which does not have three-term arithmetic progressions,
and has relatively high density. Using Behrend’s [Beh46] construction of such
a set with density $2^{-\mathcal{O}(\sqrt{\log N})}$, it follows that
$\alpha(\langle N,N,N\rangle)\geq N^{2}/2^{\mathcal{O}(\sqrt{\log N})}$.

Using the same construction of Behrend’s set, it was proved in [CFL83] that
the NOF problem $\textsc{Eval}(\mathbb{Z}_{N})$ has a deterministic protocol
with communication complexity $\mathcal{O}(\sqrt{\log N})$ — significantly
improving upon the naive $\mathcal{O}(\log N)$. We observe that their
construction of an efficient NOF protocol not only uses the same technical
ingredients as the construction of large independent set in the matrix
multiplication tensor, but in fact it is much more intimately related — known
results in communication complexity together with our connection directly
imply the Strassen result on the subrank of matrix multiplication tensor.

######  Proposition 27.

If there is any permutation problem $I\subset[N]\times[N]\times[N]$ with NOF
communication complexity $\mathcal{CC}(\tilde{I},P_{\textsc{nof}})\leq k$,
then $\alpha(\langle N,N,N\rangle)\geq N^{2}2^{-k}$.

###### Proof.

By Theorem 9, if the promise problem $(\tilde{I},P_{\textsc{nof}})$ has NOF
communication complexity $k$, then $\chi(I,P_{\textsc{nof}})\leq 2^{k}$, and
in particular taking the largest color we get $\alpha(I,P_{\textsc{nof}})\geq
n^{2}2^{-k}$. Since the promise tensor $P_{\textsc{nof}}$ for the number on
the forehead communication problems is exactly the matrix multiplication
tensor $\langle n,n,n\rangle$, we can disregard which terms are green, and
deduce $\alpha(\langle n,n,n\rangle)\geq\alpha(I,P_{\textsc{nof}})\geq
n^{2}2^{-k}$. ∎

###  3.7 Other promise problems

As we understand now, the slice rank-based approach for proving lower bounds
for asymptotic communication complexity of NOF permutation problems failed,
because the technique depends only on the promise tensor, and is insensitive
to the specific problem — and the promise tensor corresponding to the number-
on-the-forehead problems is a matrix multiplication tensor, with maximal
subrank.

With this in mind, it is worth looking at promise problems with other promise-
tensors, hopefully ones for which we know the asymptotic subrank is not
maximal — this statement alone shall imply that _every_ permutation problem
with such a promise should have positive asymptotic communication complexity.

######  Fact 28.

If the promise tensor $P$ over $\Sigma\times\Sigma\times\Sigma$ has non-
maximal asymptotic subrank

$\underline{\alpha}(P):=\lim\sup\alpha(P^{\otimes N})^{1/N}<|\Sigma|,$

then for every permutation problem $I\subset P$ we have

$\mathcal{CC}((I,P)^{\otimes N})\geq\Omega(N).$

The proof of this fact is straightforward with what we have discussed so far.
We later provide a complete proof of a strictly stronger theorem (Theorem 33),
so we leave a direct proof of this special case to the reader.

The solution of the cap-set problem [CLP17, EG16, Tao16] and its subsequent
generalizations [BCC+17], can be interpreted as saying that for any abelian
group $G$, the structure tensor

$T_{G}:=\sum_{g,h\in G}x_{g}y_{h}z_{-g-h},$

has $\underline{\alpha}(T_{G})<|G|$. In particular, all permutation problems
with a promise tensor being a structure tensor of such a group, have positive
asymptotic communication complexity. For example, the following is true

######  Corollary 29.

Consider the promise problem $\textsc{Eq}_{\mathbb{F}_{3}^{N}}$, where parties
receive inputs $x,y,z\in\mathbb{F}_{3}^{N}$ with a promise that $x+y+z=0$, and
they wish to decide whether $x=y$. This problem requires $\Omega(N)$
communication.

Without the preceding discussion it would not be immediately clear whether we
should expect this statement to be true — the relevant part of the problem is
between Alice and Bob, and they just wish to decide the equality predicate for
their inputs — a task which, with ordinary deterministic two-party protocols,
requires $\Omega(N)$ communication. But should we expect Charlie, who knows
$x+y$ to be of much help in solving the task?

On the other hand, one might think that the statement above — if true — should
be relatively straightforward to prove directly, with a proof similar to the
communication lower bound for deterministic two-party equality problem. We
observe that in fact this statement is easily _equivalent_ to the cap-set
theorem, hence a direct proof would be an interesting new proof of what used
to be a cap-set _conjecture_ for almost four decades.

######  Fact 30.

For any abelian group $G$, if there is a $S\subset G$ of size $|G|^{1-\delta}$
without three-terms arthmetic progressions, then
$\mathcal{CC}(\textsc{Eq}_{G})\leq\delta\log|G|+\mathcal{O}(\log\log|G|)$

###### Proof.

The corresponding communication tensor of a problem $\textsc{Eq}_{G}$ is
$(I,T_{G})$ where $T_{G}$ is the structure tensor of the group $G$, and
$I=\\{(x,x,-2x):x\in G\\}\subset T_{G}$.

We will first show that $\alpha(I,T_{G})\geq|S|$. We wish to show that if $S$
does not have three terms arithmetic progressions, then
$S^{\prime}:=\\{(x,x,-2x):x\in S\\}\subset I$ is an independent set. Indeed,
for the sake of contradiction, let us assume that $(x,y,-x-y)$ for some
$x\not=y$ has
$x\in\pi_{1}(S^{\prime}),y\in\pi_{2}(S^{\prime}),-x-y\in\pi_{3}(S^{\prime})$.
This means $x,y\in S$, and $-x-y=-2z$ for some $z\in S$ — i.e. $x,z,y$ is a
three terms arithmetic progression.

To lift a large independent set to a small coloring, we will refer to Lemma 17
— it is enough to show that there is an automorphism of $(I,T_{G})$ that maps
arbitrary $(x,x,-2x)$ to $(y,y,-2y)$. This is given by a triple of
permutations $\sigma_{1}=\sigma_{2}:w\mapsto w-x+y$, and $\sigma_{3}:w\mapsto
w+2y-2x$. Finally, by Theorem 9 a coloring of the tensor $(I,T_{G})$ into
$|G|^{\delta}\log|G|$ colors yields a protocol with complexity
$\delta\log|G|+\log\log|G|$. ∎

###  3.8 Lower Bounds from the Asymptotic Spectrum of Tensors

The results in this section concern promise problems which are not necessarily
permutation problems. We will first need a simple combinatorial description of
the communication complexity of such a problem.

For any transcript of a protocol $\pi$, the set of inputs
$S_{\pi}\subset\Sigma\times\Sigma\times\Sigma$ which result in such a
transcript is a combinatorial cube $A_{\pi}\times B_{\pi}\times C_{\pi}$ for
some $A_{\pi},B_{\pi},C_{\pi}\subset\Sigma$. If the protocol is correct, in
every such cube either all terms from $P$ are contained in $I$, or they all
are not in $I$. As such, a correct protocol of complexity $k$ induces a
partition of the tensor $P$ into $2^{k}$ monochromatic combinatorial cubes
(where a cube is monochromatic in the preceding sense).

In particular, for any promise problems $(I,P)$ all terms from $I$ can be
covered by $2^{\mathcal{CC}(I,P)}$ combinatorial cubes, each of which does not
contain any term in $P-I$.

######  Theorem 31.

Let $r:\mathbb{F}^{\Sigma\times\Sigma\times\Sigma}\to\mathbb{R}_{\geq 0}$ be
any function which is:

  * •

_sub-additive_ , meaning, if
$A,B\in\mathbb{F}^{\Sigma\times\Sigma\times\Sigma}$ then $r(A+B)\leq
r(A)+r(B)$, and

  * •

_monotone under zeroing outs_ , meaning, if
$A,B\in\mathbb{F}^{\Sigma\times\Sigma\times\Sigma}$ and $B$ is a zeroing out
of $A$, then $r(B)\leq r(A)$.

Suppose $P$ is any promise tensor over $\Sigma\times\Sigma\times\Sigma$, and
$I\subset P$ is any problem (not necessarily a permutation problem). Then,

$\mathcal{CC}(I,P)\geq\log_{2}\left(\frac{r(I)}{r(P)}\right).$

###### Proof.

Let $k=2^{\mathcal{CC}(I,P)}$. By the preceding discussion, there are $k$
tensors $T_{1},\ldots,T_{k}\in\mathbb{F}^{\Sigma\times\Sigma\times\Sigma}$
which are each zeroing outs of $P$, such that $T_{1}+\cdots+T_{k}=I$. We thus
have

$r(I)\leq\sum_{i=1}^{k}r(T_{i})\leq k\cdot r(P),$

as desired. ∎

Although it is relatively simple, Theorem 31 is quite powerful since there are
many well-studied examples of functions $r$ in algebraic complexity and tensor
combinatorics which are sub-additive and monotone under zeroing outs. Tensor
rank ($R$) is the most prominent example, but there are also other well-
studied rank variants such as ‘slice rank’ [Tao16] and ‘geometric rank’
[KMZ20]. (Note that subrank ($Q$) is super-additive, not sub-additive.)

##### Number In Hand

For one example, consider the all-1s tensor
$P_{NIH}\in\mathbb{F}^{\Sigma\times\Sigma\times\Sigma}$, which is the promise
tensor for the Number In Hand model. This very simple tensor has rank
$R(P_{NIH})=1$. Thus, by Theorem 31, any tensor $I$ with
$R(I)\geq|\Sigma|^{\Omega(1)}$ has essentially maximal Number In Hand
communication complexity $\Omega(\log|\Sigma|)$. Note that all tensors
$I\in\mathbb{F}^{\Sigma\times\Sigma\times\Sigma}$ have $R(I)\geq|\Sigma|$
except for tensors which are somehow “degenerate”; for instance, all ‘concise’
tensors have this property [CGL+21].

This instantiation of Theorem 31, where the promise is the all-ones tensor and
$r$ is the rank of the problem tensor $I$, is akin to the standard lower bound
in two-party deterministic communication complexity by the $\log\mathrm{rank}$
of the communication matrix. The celebrated log-rank conjecture stipulates
that in the standard setting this statement can be weakly inverted, and in
fact any two-party communication problem (with trivial promise) has a protocol
with complexity $(\log\mathrm{rank}(I))^{c}$ for some constant $c$.

##### Number On Forehead

For another example, consider the tensor
$P_{NOF}\in\mathbb{F}^{\Sigma^{2}\times\Sigma^{2}\times\Sigma^{2}}$, which is
the promise tensor for the Number On Forehead model. As we’ve seen,
$P_{NOF}=\langle|\Sigma|,|\Sigma|,|\Sigma|\rangle$, and so we know that
$R(P_{NOF})=|\Sigma|^{\omega+o(1)}$. It follows that if $I\subset P_{NOF}$ is
a problem with $R(I)\geq|\Sigma|^{c}$ for some constant $c>\omega$, then $I$
has Number On Forehead communication complexity
$\geq(c-\omega+o(1))\log|\Sigma|$.

This relates the classic open problem in algebraic complexity of finding high-
rank tensors to the task of proving deterministic NOF lower bounds.
Furthermore, the fact that $\omega$, the exponent of matrix multiplication, is
_subtracted_ in the communication lower bound is intriguing. This means that
designing faster matrix multiplication algorithms, and hence decreasing our
best-known upper bound on $\omega$, actually makes it _easier_ to prove NOF
_lower bounds_ via this approach.

####  3.8.1 Generalization to the Asymptotic Spectrum

Finally, in this section, we note that while subrank is not sub-additive, the
zeroing out variant ($Q_{ZO}$) we have been studying is additive (and hence
sub-additive) for direct sums, and so a similar version of Theorem 31 still
holds for it. Moreover, this holds for any $r$ in the ‘asymptotic spectrum of
tensors’ [Str86, WZ22], a well-studied class which roughly captures the
different ways to generalize the notion of the ‘rank’ of a matrix to tensors.

######  Definition 32.

Tensor $B$ is an _identification_ of tensor $A$ if you can get to $B$ from $A$
by first doing a zeroing out then setting some variables equal to each other.
For example, $B=x_{0}y_{0}z_{0}+x_{0}y_{1}z_{1}$ is an identification of
$A=x_{0}y_{0}z_{0}+x_{1}y_{1}z_{1}+x_{0}y_{1}z_{2}$ by zeroing out $z_{2}$ and
setting $x_{1}\leftarrow x_{0}$. Identifications generalize zeroing outs, but
are a special case of tensor restrictions.

######  Theorem 33.

Let $r:\mathbb{F}^{\Sigma\times\Sigma\times\Sigma}\to\mathbb{R}_{\geq 0}$ be
any function which is:

  * •

_sub-additive for direct sums_ , meaning, if
$A\in\mathbb{F}^{\Sigma\times\Sigma\times\Sigma}$ and
$B\in\mathbb{F}^{\Sigma^{\prime}\times\Sigma^{\prime}\times\Sigma^{\prime}}$
are tensors for disjoint sets $\Sigma,\Sigma^{\prime}$, then $r(A+B)\geq
r(A)+r(B)$, where $A+B$ is a tensor over
$\mathbb{F}^{\Sigma\cup\Sigma^{\prime}\times\Sigma\cup\Sigma^{\prime}\times\Sigma\cup\Sigma^{\prime}}$
and

  * •

_monotone under identifications_ , meaning, if
$A,B\in\mathbb{F}^{\Sigma\times\Sigma\times\Sigma}$ and $B$ is an
identification of $A$, then $r(B)\leq r(A)$.

Suppose $P$ is any promise tensor over $\Sigma\times\Sigma\times\Sigma$, and
$I\subset P$ is any problem (not necessarily a permutation problem). Then,

$\mathcal{CC}(I,P)\geq\log_{2}\left(\frac{r(I)}{r(P)}\right).$

###### Proof.

Let $k=2^{\mathcal{CC}(I,P)}$. By definition, there are $k$ tensors
$T_{1},\ldots,T_{k}\in\mathbb{F}^{\Sigma\times\Sigma\times\Sigma}$ which are
each zeroing outs of $P$, such that $T_{1}+\cdots+T_{k}=I$. In particular, the
direct sum of $k$ copies of $P$ has a zeroing out to the direct sum of all the
$T_{i}$ tensors, which in turn has an identification to $I$. We thus have

$r(I)\leq\sum_{i=1}^{k}r(T_{i})\leq k\cdot r(P),$

as desired. ∎

######  Fact 34.

The zeroing out subrank $r=Q_{ZO}$ satisfies the premises of Theorem 33.

###### Proof.

$Q_{ZO}$ is sub-additive for direct sums since any zeroing out of a direct sum
to a diagonal tensor must separately zero out each part into a diagonal
tensor. It’s monotone under identifications since, when transforming a tensor
$A$ to a diagonal tensor via identification, we may assume that we first
perform a zeroing out and then set variables equal to each other, but setting
variables equal to each other cannot increase the size of a diagonal tensor. ∎

###  3.9 Intermediate Group Promise Problems

Suppose $T_{1}\subset T_{2}\subset T_{3}$ are $\\{0,1\\}$-valued tensors.
These give rise to three promise problems, depending on which one picks as the
promise and which one picks as the problem: $(T_{1},T_{2})$, $(T_{1},T_{3})$,
and $(T_{2},T_{3})$. We observe a simple triangle inequality-type relationship
between their communication complexities:

######  Fact 35.

$\mathcal{CC}(T_{1},T_{3})\leq\mathcal{CC}(T_{1},T_{2})+\mathcal{CC}(T_{2},T_{3})$

###### Proof.

In order to solve $(T_{1},T_{3})$, first use a protocol for $(T_{2},T_{3})$ to
determine whether the input is in $T_{2}$, then use a protocol for
$(T_{1},T_{2})$ to determine whether the input is in $T_{1}$. ∎

We will now consider a particular instantiation of 35 which yields a potential
avenue toward proving deterministic NOF lower bounds. $T_{1},T_{2},T_{3}$ will
be tensors from $\mathbb{F}^{\Sigma^{2}\times\Sigma^{2}\times\Sigma^{2}}$ for
some finite set $\Sigma$. Let $n:=|\Sigma|$.

We will pick $T_{3}$ to be the structure tensor of the group
$(\mathbb{Z}/n\mathbb{Z})^{2}$. This tensor is typically written

$T_{3}=\sum_{a,b,c,d\in[n]}x_{(a,b)}y_{(c,d)}z_{(a+c,b+d)},$

where additions in the subscripts (here and in the remainder of this
subsection) are done mod $n$. However, to simplify the next step, we can
permute the variable names (replacing $x_{(a,b)}$ with $x_{(a+b,b)}$ for all
$a,b\in[n]$, replacing $y_{(c,d)}$ with $y_{(c,c+d)}$ for all $c,d\in[n]$, and
replacing $z_{(a+c,b+d)}$ with $z_{(b+d,a+c)}$ for all $a,b,c,d\in[n]$) to
equivalently write it as

$T_{3}=\sum_{a,b,c,d\in[n]}x_{(a+b,b)}y_{(c,d+c)}z_{(b+d,a+c)}.$

Next, we will pick $T_{2}=P_{\textsc{nof}}\in\mathbb{F}^{n^{2}\times
n^{2}\times n^{2}}$ to be the Number On Forehead promise tensor, i.e., the
$\langle n,n,n\rangle$ matrix multiplication tensor,

$T_{2}=\sum_{i,j,k\in[n]}x_{(i,j)}y_{(j,k)}z_{(k,i)}.$

######  Fact 36.

$T_{2}\subset T_{3}$.

###### Proof.

For each $i,j,k\in[n]$, we need to prove that there is a choice of
$a,b,c,d\in[n]$ such that
$x_{(i,j)}y_{(j,k)}z_{(k,i)}=x_{(a+b,b)}y_{(c,d+c)}z_{(b+d,a+c)}$. The choice
which achieves this is $b=c=j$, $a=i-j\pmod{n}$, and $d=k-j\pmod{n}$. ∎

Finally, we may pick $T_{1}$ to be any Number On Forehead problem
$T_{1}\subset T_{2}$. 35 now relates the Number On Forehead complexity of the
problem $T_{1}$ to two different promise problems with the promise $T_{3}$:

$\mathcal{CC}(T_{1},P_{NOF})\geq\mathcal{CC}(T_{1},T_{3})-\mathcal{CC}(P_{NOF},T_{3}).$

Using the tools we’ve developed thusfar, we can bound the communication
complexity $\mathcal{CC}(P_{NOF},T_{3})$. Note that these are tensors over
$\mathbb{F}^{n^{2}\times n^{2}\times n^{2}}$, so the trivial communication
upper bound would be $2\log n$.

######  Lemma 37.

$(\omega-2)\log n\leq\mathcal{CC}(P_{NOF},T_{3})\leq\log(n).$

###### Proof.

Since $P_{NOF}$ is the $\langle n,n,n\rangle$ matrix multiplication tensor,
its rank is $R(P_{NOF})=n^{\omega+o(1)}$. Meanwhile, since $T_{3}$ is the
structure tensor of an abelian group, its rank is $R(T_{3})=n^{2}$ (see, e.g.,
[CU03, Theorem 2.3 and Theorem 4.1]). Thus, Theorem 31 yields the lower bound
$(\omega-2)\log n\leq\mathcal{CC}(P_{NOF},T_{3})$.

For the upper bound, we directly give a communication protocol. In this
problem, player $A$ is given $(a+b,b)$, player $B$ is given $(c,d+c)$, and
player $C$ is given $(b+d,a+c)$, for some values $a,b,c,d\in\mathbb{Z}_{n}$,
and their goal is to determine whether or not the following three equalities
hold: $b=c$, $d+c=b+d$, and $a+c=a+b$. Note that this is equivalent to testing
whether $b=c$, since the other two equalities follow from this. They can do
this by having player $A$ send $b$, which uses $\log n$ bits, and then having
player $B$ confirm that it is equal to $c$. ∎

Interestingly, in light of the lower bound in Lemma 37, we know that improving
the upper bound $\mathcal{CC}(P_{NOF},T_{3})\leq\log(n)$ _requires_ using fast
matrix multiplication. Indeed, any bound
$\mathcal{CC}(P_{NOF},T_{3})\leq(1-\delta)\log(n)$ would imply that
$\omega<3-\delta$. More specifically, one can observe that an upper bound on
$\omega$ obtained in this way would fall under the ‘group-theoretic approach’
to matrix multiplication [CU03], using the group
$(\mathbb{Z}/n\mathbb{Z})^{2}$. There are known barriers to this approach for
any fixed $n$ [BCC+17], but it’s consistent with the best-known barriers that
this approach could prove $\omega=2$ by using increasingly larger $n$. (On the
other hand, most recent work on the group-theoretic approach has focused
instead on non-abelian groups [BCG+22].)

Combining Lemma 37 together with 35 shows that

######  Fact 38.

$\mathcal{CC}(T_{1},P_{NOF})\geq\mathcal{CC}(T_{1},T_{3})-\log(n).$

For any $T_{1}$, the straightforward algorithm for the problem $(T_{1},T_{3})$
has communication complexity $2\log(n)$. 38 shows that any $T_{1}$ with
$\mathcal{CC}(T_{1},T_{3})\geq(1+\delta)\log(n)$ for any fixed $\delta>0$
would give a linear Number On Forehead lower bound
$\mathcal{CC}(T_{1},P_{NOF})\geq\Omega(\log n)$.

In light of this, improving the upper bound of Lemma 37 could be quite
powerful. In particular, if $\omega=2$, and if this can be used to give an
algorithm achieving $\mathcal{CC}(P_{NOF},T_{3})\leq o(\log(n))$, then any
$T_{1}$ with $\mathcal{CC}(T_{1},T_{3})\geq\Omega(\log(n))$ (without any
restriction on the leading constant) would give a linear Number On Forehead
lower bound $\mathcal{CC}(T_{1},P_{NOF})\geq\Omega(\log n)$ as well.

##### Acknowledgements

The authors thank Madhu Sudan and Toniann Pitassi for helpful discussions.

## References

  * [Alm21] Josh Alman.  Limits on the universal method for matrix multiplication.  Theory Of Computing, 17(1):1–30, 2021.
  * [AMS12] Noga Alon, Ankur Moitra, and Benny Sudakov.  Nearly complete graphs decomposable into large induced matchings and their applications.  In Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing, STOC ’12, page 1079–1090, New York, NY, USA, 2012. Association for Computing Machinery.
  * [AS20] Noga Alon and Adi Shraibman.  Algorithmic number on the forehead protocols yielding dense ruzsa-szemerédi graphs and hypergraphs, 2020.
  * [AW21] Josh Alman and Virginia Vassilevska Williams.  Limits on all known (and some unknown) approaches to matrix multiplication.  SIAM Journal on Computing, (0):FOCS18–285, 2021.
  * [BCC+17] 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 Analysis, 3, 2017.
  * [BCG+22] Jonah Blasiak, Henry Cohn, Joshua A Grochow, Kevin Pratt, and Chris Umans.  Matrix multiplication via matrix groups.  arXiv preprint arXiv:2204.03826, 2022.
  * [BDPW10] Paul Beame, Matei David, Toniann Pitassi, and Philipp Woelfel.  Separating deterministic from randomized multiparty communication complexity.  Theory of Computing, 6(1):201–225, 2010.
  * [Beh46] Felix A Behrend.  On sets of integers which contain no three terms in arithmetical progression.  Proceedings of the National Academy of Sciences, 32(12):331–332, 1946.
  * [Bin05] Dario Bini.  Border rank of ap$\times$ q$\times$ 2 tensor and the optimal approximation of a pair of bilinear forms.  In Automata, Languages and Programming: Seventh Colloquium Noordwijkerhout, the Netherlands July 14–18, 1980, pages 98–108. Springer, 2005\.
  * [Blä13] Markus Bläser.  Fast matrix multiplication.  Theory of Computing, pages 1–60, 2013.
  * [BT94] Richard Beigel and Jun Tarui.  On acc.  Computational Complexity, 4:350–366, 1994.
  * [CEMS91] Lane H Clark, Roger C Entringer, Joseph E McCanna, and László A Székely.  Extremal problems for local properties of graphs.  Australas. J Comb., 4:25–32, 1991.
  * [CFL83] Ashok K Chandra, Merrick L Furst, and Richard J Lipton.  Multi-party protocols.  In Proceedings of the fifteenth annual ACM symposium on Theory of computing, pages 94–99, 1983.
  * [CFTZ21] Matthias Christandl, Omar Fawzi, Hoang Ta, and Jeroen Zuiddam.  Symmetric subrank of tensors and applications, 2021.
  * [CFTZ22] Matthias Christandl, Omar Fawzi, Hoang Ta, and Jeroen Zuiddam.  Larger corner-free sets from combinatorial degenerations.  Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.
  * [CGL+21] Austin Conner, Fulvio Gesmundo, Joseph M Landsberg, Emanuele Ventura, and Yao Wang.  Towards a geometric approach to strassen’s asymptotic rank conjecture.  Collectanea mathematica, 72:63–86, 2021.
  * [CLP17] Ernie Croot, Vsevolod F Lev, and Péter Pál Pach.  Progression-free sets in are exponentially small.  Annals of Mathematics, pages 331–337, 2017.
  * [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., pages 438–449. IEEE, 2003.
  * [CVZ21] Matthias Christandl, Péter Vrana, and Jeroen Zuiddam.  Barriers for fast matrix multiplication from irreversibility.  THEORY OF COMPUTING, 17(2):1–32, 2021.
  * [CW87] Don Coppersmith and Shmuel Winograd.  Matrix multiplication via arithmetic progressions.  In Proceedings of the nineteenth annual ACM symposium on Theory of computing, pages 1–6, 1987.
  * [DP08] Matei David and Toniann Pitassi.  Separating nof communication complexity classes rp and np, 2008.
  * [EG16] Jordan S. Ellenberg and Dion Gijswijt.  On large subsets of $f_{q}^{n}$ with no three-term arithmetic progression, 2016.
  * [Fox11] Jacob Fox.  A new proof of the graph removal lemma.  Annals of Mathematics, pages 561–579, 2011.
  * [HG90] J. Hastad and M. Goldmann.  On the power of small-depth threshold circuits.  In Proceedings [1990] 31st Annual Symposium on Foundations of Computer Science, pages 610–618 vol.2, 1990.
  * [KMZ20] Swastik Kopparty, Guy Moshkovitz, and Jeroen Zuiddam.  Geometric rank of tensors and subrank of matrix multiplication.  arXiv preprint arXiv:2002.09472, 2020.
  * [LPS19] Nati Linial, Toniann Pitassi, and Adi Shraibman.  On the communication complexity of high-dimensional permutations, 2019\.
  * [LS21] Nati Linial and Adi Shraibman.  Larger corner-free sets from better nof exactly-$n$ protocols, 2021.
  * [RS78] Imre Z Ruzsa and Endre Szemerédi.  Triple systems with no six points carrying three triangles.  Combinatorics (Keszthely, 1976), Coll. Math. Soc. J. Bolyai, 18(939-945):2, 1978.
  * [Str73] Volker Strassen.  Vermeidung von divisionen.  Journal für die reine und angewandte Mathematik, 264:184–202, 1973.
  * [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. IEEE, 1986.
  * [Str87] V Strassen.  Relative bilinear complexity and matrix multiplication.  Journal für die reine und angewandte Mathematik, 375:406–443, 1987.
  * [Tao16] Terence Tao.  A symmetric formulation of the croot-lev-pach-ellenberg-gijswijt capset bound.  blog post, 2016.
  * [VLW01] Jacobus Hendricus Van Lint and Richard Michael Wilson.  A course in combinatorics.  Cambridge university press, 2001.
  * [WZ22] Avi Wigderson and Jeroen Zuiddam.  Asymptotic spectra: Theory, applications and extensions, 2022.