# Matrix Multiplication Verification Using Coding Theory

Huck Bennett Oregon State University. Email<EMAIL_ADDRESS>Karthik
Gajulapalli Georgetown University. Email<EMAIL_ADDRESS>Alexander
Golovnev Georgetown University. Email<EMAIL_ADDRESS>Philip G.
Warton Oregon State University. Email<EMAIL_ADDRESS>
###### Abstract

We study the _Matrix Multiplication Verification Problem_ (MMV) where the goal
is, given three $n\times n$ matrices $A$, $B$, and $C$ as input, to decide
whether $AB=C$. A classic randomized algorithm by Freivalds (MFCS, 1979)
solves MMV in $\widetilde{O}(n^{2})$ time, and a longstanding challenge is to
(partially) derandomize it while still running in faster than matrix
multiplication time (i.e., in $o(n^{\omega})$ time).

To that end, we give two algorithms for MMV in the case where $AB-C$ is
_sparse_. Specifically, when $AB-C$ has at most $O(n^{\delta})$ non-zero
entries for a constant $0\leq\delta<2$, we give (1) a deterministic
$O(n^{\omega-\varepsilon})$-time algorithm for constant
$\varepsilon=\varepsilon(\delta)>0$, and (2) a randomized
$\widetilde{O}(n^{2})$-time algorithm using $\delta/2\cdot\log_{2}n+O(1)$
random bits. The former algorithm is faster than the deterministic algorithm
of Künnemann (ESA, 2018) when $\delta\geq 1.056$, and the latter algorithm
uses fewer random bits than the algorithm of Kimbrel and Sinha (IPL, 1993),
which runs in the same time and uses $\log_{2}n+O(1)$ random bits (in turn
fewer than Freivalds’s algorithm).

Our algorithms are simple and use techniques from coding theory. Let $H$ be a
parity-check matrix of a Maximum Distance Separable (MDS) code, and let
$G=(I_{k}\;|\;G^{\prime})$ be a generator matrix of a (possibly different) MDS
code in systematic form. Our deterministic algorithm uses fast rectangular
matrix multiplication to check whether $HAB=HC$, and our randomized algorithm
samples a uniformly random column $\boldsymbol{g}^{\prime}$ from $G^{\prime}$
and checks whether $AB\boldsymbol{g}^{\prime}=C\boldsymbol{g}^{\prime}$.

We additionally study the _complexity_ of MMV. We first show that all
algorithms in a natural class of deterministic linear algebraic algorithms for
MMV (including ours) require $\Omega(n^{\omega})$ time. We also show a barrier
to proving a super-quadratic running time lower bound for matrix
multiplication (and hence MMV) under the Strong Exponential Time Hypothesis
(SETH). Finally, we study relationships between natural variants and special
cases of MMV (with respect to deterministic $\widetilde{O}(n^{2})$-time
reductions).

###### Contents

  1. 1 Introduction
    1. 1.1 Our Results
      1. 1.1.1 Algorithms
      2. 1.1.2 Barriers
      3. 1.1.3 Reductions
    2. 1.2 Related Work
    3. 1.3 Open Questions
    4. 1.4 Acknowledgments
  2. 2 Preliminaries
    1. 2.1 Matrix Multiplication
    2. 2.2 Matrix Multiplication Verification
    3. 2.3 Coding Theory
    4. 2.4 Regular and Super Regular Matrices
    5. 2.5 Fine-Grained Complexity
    6. 2.6 Matrix Rigidity and Circuit Lower Bounds
  3. 3 Fast Matrix Multiplication Verification for Sparse Matrices
    1. 3.1 Deterministic MMV for Sparse Matrices
    2. 3.2 Randomized MMV for Sparse Matrices
    3. 3.3 A Barrier for Linear Algebraic Approaches to MMV
  4. 4 On the non-SETH-hardness of Matrix Multiplication
    1. 4.1 A Nondeterministic Algorithm for Multiplying Non-Rigid Matrices
    2. 4.2 The Main SETH-Hardness Barrier Result
    3. 4.3 Comparison with Known Rigidity Results
  5. 5 Reductions Between Variants of MMV
    1. 5.1 Problems Equivalent to MMV
      1. 5.1.1 Inverse Verification
      2. 5.1.2 Symmetric MMV
    2. 5.2 Problems no Harder than MMV
      1. 5.2.1 Monochromatic All Pairs Orthogonal Vectors
      2. 5.2.2 Strong Symmetric MMV
    3. 5.3 Problems at Least as Hard as MMV but no Harder than MM
      1. 5.3.1 Generalized AllZeroes Equivalence
      2. 5.3.2 Relation to Orthogonal Vectors and Matrix-Product-Sparsity

##  1 Introduction

The goal of the _Matrix Multiplication Problem_ (MM) is to compute the product
$AB$ of two $n\times n$ matrices $A$ and $B$ given as input. Matrix
multiplication has many practical and theoretical applications, and because of
this has been studied by an extensive line of work. The primary goal of this
work has been to determine the running time $O(n^{\omega})$ of the fastest
algorithms for MM, which is captured by the matrix multiplication exponent
$\omega$.111Formally, $\omega$ is defined as the infimum over
$\omega^{\prime}$ such that the product of two $n\times n$ matrices can be
computed in $O(n^{\omega^{\prime}})$ time. So, MM algorithms are actually only
guaranteed to run in $O(n^{\omega+\varepsilon})$ time for any constant
$\varepsilon>0$. The best upper bounds on $\omega$ and related quantities
continue to improve [LU18, AV21, DWZ23, LG23, VXXZ23], and [VXXZ23] recently
showed the current best known bound of $\omega\leq 2.371552$. The dream of
this line of work is to show that $\omega=2$, and this in fact holds under
certain plausible combinatorial and group-theoretic conjectures (see [CKSU05,
Conjecture 4.7 and Conjecture 3.4]). Nevertheless, showing that $\omega=2$
seems very challenging for the time being.

In this work, we consider a variant of matrix multiplication where the goal is
to _verify_ that the product of two matrices is equal to a third matrix.
Specifically, we study the _Matrix Multiplication Verification Problem_ (MMV)
where, given three $n\times n$ matrices $A$, $B$, and $C$ as input, the goal
is to decide whether $AB=C$. MMV is clearly no harder than matrix
multiplication—it can be solved in $O(n^{\omega})$ time by computing the
product $AB$ and then comparing the product entry-wise against $C$—but it is
natural to ask whether it is possible to do better. In what became classic
work, Freivalds [Fre79] answered this question in the affirmative and gave a
simple, randomized algorithm that solves MMV in $\widetilde{O}(n^{2})$ time.
This $\widetilde{O}(n^{2})$ running time bound is essentially the best
possible, and so, unlike matrix multiplication, the complexity of MMV is
relatively well understood.

However, it is in turn natural to ask whether it is possible to _derandomize_
Freivalds’s algorithm partially or completely. More specifically, it is
natural to ask whether it is possible to give a _deterministic_ algorithm for
MMV running in $\widetilde{O}(n^{2})$ time or at least
$O(n^{\omega-\varepsilon})$ time for constant $\varepsilon>0$.222We use the
notation $\widetilde{O}(f(n))$ to mean $f(n)\cdot\operatorname{poly}(\log
f(n))$. Freivalds’s algorithm uses $O(n^{2})$ arithmetic operations, each of
which takes $\operatorname{poly}(\log n)$ time when working over integer
matrices with entries bounded in magnitude by $\operatorname{poly}(n)$; we
assume this setting in the introduction.
Of course, it is only possible for such a $O(n^{\omega-\varepsilon})$-time
algorithm to exist if $\omega>2$. We assume that this is the case throughout
the introduction. Or, if it is not possible to give a deterministic algorithm
for MMV with these running times, it is natural to ask whether it is possible
to use fewer random bits than Freivalds’s algorithm, which uses $n$ random
bits. Trying to answer these questions has become a key goal for
derandomization efforts, and has received substantial study [AGHP90, KS93,
KW14, Kün18].

Algorithm | Asymptotic Runtime | Bits of Randomness
---|---|---
Matrix Multiplication | $n^{\omega+\varepsilon}$ | 0
Random Entry Sampling (folklore) | $n^{3-\delta}$ | $2n^{2-\delta}\cdot\log_{2}(n)+O(1)$
Freivalds’s Algorithm [Fre79] | $n^{2}$ | $n$
Vandermonde Mat. Sampling [KS93] | $n^{2}$ | $\log_{2}(n)+O(1)$
Multipoint Poly. Evaluation [Kün18] | $n^{2}+n^{1+\delta}$ | 0
Cauchy Bound [KW14] |  $n^{3}$ ($n^{2}$ in Integer RAM) | 0
Parity Check/Fast RMM (Thm. 1.1) | $n^{\omega(1,1,\delta/2)+\varepsilon}$ | 0
Cauchy Mat. Sampling (Thm. 1.2) | $n^{2}$ | $\frac{\delta}{2}\cdot\log_{2}(n)$
Table 1:  Algorithms for MMV on matrices $A,B,C\in\mathbb{Z}^{n\times n}$ with
entries of magnitude at most $\operatorname{poly}(n)$ and such that $AB-C$ has
at most $n^{\delta}$ non-zero entries for $0\leq\delta\leq 2$. Our new
algorithms are shown in bold. We list asymptotic running times, with
$\operatorname{poly}(\log n)$ factors suppressed for readability, and the
number of random bits used to achieve success probability $1/2$. (Each of the
three listed randomized algorithms has one-sided error, so this probability is
meaningful.) Here $\omega(\cdot,\cdot,\cdot)$ is the rectangular matrix
multiplication exponent, $\omega=\omega(1,1,1)$ is the (square) matrix
multiplication exponent, and $\varepsilon>0$ is an arbitrarily small positive
constant.

###  1.1 Our Results

Our main results are two new algorithms for the Matrix Multiplication
Verification Problem in the _sparse_ case, i.e., in the case where $AB-C$ is
promised to have few non-zero entries (if any). See Table 1 for a summary of
our algorithms and how they compare to other known algorithms for MMV.
Additionally, we give a barrier for giving a fast algorithm for MMV using a
broad class of linear algebraic techniques, a barrier to showing hardness of
MMV, and reductions between variants of MMV.

####  1.1.1 Algorithms

We define $\lVert\boldsymbol{v}\rVert_{0}$ (respectively, $\lVert
M\rVert_{0}$) to be the number of non-zero entries in (i.e., Hamming weight
of) a vector $\boldsymbol{v}$ (respectively, matrix $M$). We call a vector
$\boldsymbol{v}$ (respectively, matrix $M$) _$t$ -sparse_ if
$\lVert\boldsymbol{v}\rVert_{0}\leq t$ (respectively, if $\lVert
M\rVert_{0}\leq t$).

Our first algorithm is deterministic, and uses fast rectangular matrix
multiplication. For $\alpha,\beta,\gamma\in[0,1]$, let the rectangular matrix
multiplication exponent $\omega(\alpha,\beta,\gamma)$ be the infimum over
values $\omega^{\prime}>0$ such that the product of a $n^{\alpha}\times
n^{\beta}$ matrix and a $n^{\beta}\times n^{\gamma}$ matrix can be computed
using $O(n^{\omega^{\prime}})$ arithmetic operations. Note that
$\omega=\omega(1,1,1)$ is the standard (square) matrix multiplication
exponent.

######  Theorem 1.1 (Fast deterministic MMV for sparse matrices, informal).

Let $A,B,C\in\mathbb{Z}^{n\times n}$ be matrices satisfying
$\max_{i,j}\\{{\left|{A_{i,j}}\right|,\left|{B_{i,j}}\right|,\left|{C_{i,j}}\right|}\\}\leq
n^{c}$ for some constant $c>0$ and satisfying
$\lVert AB-C\rVert_{0}\leq n^{\delta}$ for $0\leq\delta\leq 2$. Then for any
constant $\varepsilon>0$, there is a deterministic algorithm for MMV on input
$A,B,C$ that runs in $O(n^{\omega(1,1,\delta/2)+\varepsilon})$ time.

We note that $\omega(1,1,\beta)<\omega$ for all $\beta<1$ (assuming
$\omega>2$; see Theorem 2.3), and so our algorithm is faster than matrix
multiplication when $AB-C$ is promised to be $O(n^{\delta})$-sparse for
constant $\delta<2$. Furthermore, it is faster than Künnemann’s algorithm
[Kün18], which is also for MMV in the regime where $AB-C$ is sparse, when
$\omega(1,1,\delta/2)<1+\delta$. The equation $\omega(1,1,\delta/2)=1+\delta$
turns out to be relevant in other contexts too [Zwi02], and both [LU18,
VXXZ23] provide bounds on its (unique) solution. Specifically, [VXXZ23] shows
that the solution $\delta$ to this equation satisfies $\delta\leq 1.056$, and
so the algorithm in Theorem 1.1 is (strictly) faster than any previously known
deterministic algorithm for MMV when $1.056\leq\delta<2$.

Additional bounds on $\omega(1,\delta/2,1)=\omega(1,1,\delta/2)$—and hence the
running time of the algorithm in Theorem 1.1—appear in [VXXZ23, Table 1]. For
example, that table shows that $\omega(1,1,0.55)<2.067$ and
$\omega(1,1,0.95)<2.333$ (which correspond to $\delta=1.1$ and $\delta=1.9$,
respectively). We also note that our algorithm runs in essentially optimal
$\widetilde{O}(n^{2})$ time when $\delta\leq 0.642\leq 2\omega^{\perp}$, where
$\omega^{\perp}:=\sup\\{{\omega^{\prime}>0:\omega(1,1,\omega^{\prime})=2}\\}\geq
0.321$ is the dual matrix multiplication exponent [VXXZ23], but that
Künnemann’s algorithm [Kün18] runs in $\widetilde{O}(n^{2})$ time for any
$\delta\leq 1$.

Our second algorithm runs in $\widetilde{O}(n^{2})$ time, but is randomized.
It uses few bits of randomness when $AB-C$ is sparse.

######  Theorem 1.2 (Fast randomized MMV for sparse matrices, informal).

Let $c>0$ be a constant, let $A,B,C\in\mathbb{Z}^{n\times n}$ be matrices
satisfying
$\max_{i,j}\\{{\left|{A_{i,j}}\right|,\left|{B_{i,j}}\right|,\left|{C_{i,j}}\right|}\\}\leq
n^{c}$ and satisfying
$\lVert AB-C\rVert_{0}\leq n^{\delta}$ for $0\leq\delta\leq 2$, and let
$\varepsilon=\varepsilon(n)\geq 1/n$. Then there is a randomized algorithm for
MMV on input $A,B,C$ that runs in $\widetilde{O}(n^{2})$ time, succeeds with
probability $1-\varepsilon$, and uses at most
$\lceil\delta/2\cdot\log_{2}(n)+\log_{2}(1/\varepsilon)\rceil$ bits of
randomness.

Theorem 1.2 improves on the number of random bits used by the algorithm of
Kimbrel and Sinha [KS93] when $\delta<2$ (which uses
$\log_{2}(n)+\log_{2}(1/\varepsilon)+O(1)$ random bits regardless of the
sparsity of $AB-C$), and matches the number of random bits used by their
algorithm when $\delta=2$. The algorithms both run in $\widetilde{O}(n^{2})$
time. In fact, one may think of the algorithm summarized in Theorem 1.2 as a
natural extension of the algorithm in [KS93] to handle the sparse case more
efficiently, although it requires additional techniques to implement. (Our
algorithm requires matrices with a stronger pseudorandomness property than
theirs; see the “algorithmic techniques” section below.)

We note that Theorem 1.2 only improves on known algorithms when $1<\delta<2$,
and only by a factor of $\delta/2$. Indeed, as mentioned above, when
$\delta\leq 1$ Künnemann’s algorithm [Kün18] solves MMV _deterministically_ in
$\widetilde{O}(n^{2})$ time, and when $\delta=2$ our algorithm matches the
number of random bits used by Kimbrel and Sinha’s algorithm. Although
seemingly modest, this constant-factor improvement is not surprising: any
super-constant improvement on the number of bits used by [KS93] (i.e., an MMV
algorithm using $o(\log n)$ random bits) could be turned into a deterministic
algorithm for MMV with only a sub-polynomial (i.e., $n^{o(1)}$) multiplicative
increase in running time.

##### Algorithmic techniques.

Here we briefly summarize the techniques that we use for the MMV algorithms
corresponding to Theorems 1.1 and 1.2. We start by remarking that Theorems 1.1
and 1.2 hold not just for matrices over $\mathbb{Z}$ with entries of
polynomial magnitude, but also for matrices over all finite fields
$\mathbb{F}_{q}$ with $q\leq\operatorname{poly}(n)$.333The algorithms also
work over larger finite fields, but with slower running times due to the
increased bit complexity of performing arithmetic operations over those
fields. In fact, our algorithms work “natively” in the finite field
setting—i.e., on $n\times n$ matrices $A,B,C$ over finite fields
$\mathbb{F}_{q}$—which is directly amenable to using techniques from coding
theory. We assume this setting in the description below.

For both algorithms, we will use the observation that if $AB-C$ is $t$-sparse
then at least one row or column of $AB-C$ must be non-zero and $k$-sparse for
$k:=\lfloor\sqrt{t}\rfloor$. A similar observation appears in [WW23].

Our first, deterministic algorithm (Theorem 1.1) uses a matrix $H$ over
$\mathbb{F}_{q}$ such that any $k$ columns of $H$ are linearly independent.
Equivalently, we require a matrix $H\in\mathbb{F}_{q}^{m\times n}$ such that
for all non-zero vectors $\boldsymbol{x}\in\mathbb{F}_{q}^{n}$ with
$\lVert\boldsymbol{x}\rVert_{0}\leq k$ (corresponding to a sparse, non-zero
column or row of $AB$), $H\boldsymbol{x}\neq\boldsymbol{0}$. This is exactly
the property guaranteed by the parity-check matrix $H$ of an error correcting
code $\mathcal{C}\subseteq\mathbb{F}_{q}^{n}$ with minimum distance $d>k$.
Moreover, if a code $\mathcal{C}$ with minimum distance $d=k+1$ is a so-called
Maximum Distance Separable (MDS) code, then it has a $k\times n$ parity-check
matrix $H$. MDS codes with useful parameters exist and have efficiently
constructible parity-check matrices. In particular, (generalized) Reed-Solomon
codes are MDS codes, and exist when $k\leq n\leq q$ (see, e.g., [Hal]). Their
parity-check matrices $H$ are Vandermonde matrices, which are constructible in
$kn\cdot\operatorname{poly}(\log q)\leq n^{2}\cdot\operatorname{poly}(\log q)$
time.

Our algorithm then uses fast rectangular matrix multiplication to compute
$HAB=(HA)B$ and $H(AB)^{T}=(HB^{T})A^{T}$ using roughly
$n^{\omega(1,1,\delta/2)}$ arithmetic operations, where $0\leq\delta\leq 2$ is
such that $t\leq n^{\delta}$. If $AB=0$, then $HAB=H(AB)^{T}=0$. On the other
hand, if $AB\neq 0$ then $AB$ is $t$-sparse and therefore has a $k$-sparse row
or column. So, at least one of the expressions $HAB$ and $H(AB)^{T}$ is non-
zero.

Our second, randomized algorithm (Theorem 1.2) uses a matrix
$S\in\mathbb{F}_{q}^{m\times n}$ with the property that all of its $k\times k$
submatrices are non-singular. Matrices $S$ with this property are called _$k$
-regular_, and matrices $S$ all of whose square submatrices (of any size) are
non-singular are called _super regular_ (see also the definitions in Section
2.4). We note that $k$-regularity is stronger than the property we require for
$H$ in the first algorithm. In particular, if a matrix
$S\in\mathbb{F}_{q}^{m\times n}$ is $k$-regular and
$0<\lVert\boldsymbol{x}\rVert_{0}\leq k$, then $\lVert
S\boldsymbol{x}\rVert_{0}\geq m-k+1$. I.e., $S$ being $k$-regular implies not
only that $S\boldsymbol{x}$ is non-zero, but that $S\boldsymbol{x}$ has
relatively high Hamming weight for such $\boldsymbol{x}$. This property is
useful because it implies that
$\Pr[\langle\boldsymbol{s},\boldsymbol{x}\rangle\neq 0]\geq(m-k+1)/m$, where
$\boldsymbol{s}$ is a random row of $S$. Indeed, this observation leads to our
second algorithm: we sample a random row $\boldsymbol{s}$ from a $k$-regular
matrix $S\in\mathbb{F}_{q}^{m\times n}$ and check whether
$\boldsymbol{s}AB=\boldsymbol{0}$ and $\boldsymbol{s}(AB)^{T}=\boldsymbol{0}$.
Setting, e.g., $m=2k$, we get that this algorithm succeeds with probability at
least $(2k-k+1)/(2k)>1/2$.

It remains to construct (rows of) $k$-regular matrices $S$ efficiently.
Although a priori it is not even obvious that $k$-regular matrices exist for
arbitrarily large $k$, in fact _super regular_ matrices exist and are
efficiently constructible. Specifically, we use a family of super regular (and
hence $k$-regular) matrices called _Cauchy matrices_ ; the entries of such a
matrix $S$ are defined as $S_{i,j}=1/(x_{i}-y_{j})$, where
$x_{1},\ldots,x_{m},y_{1},\ldots,y_{n}$ are distinct elements of
$\mathbb{F}_{q}$. In fact, as follows from their definition, given a (random)
index $1\leq i\leq m$, it is even possible to construct the $i$th row of a
Cauchy matrix $S$ efficiently without computing the rest of the matrix, as
needed.

Finally, we remark that there is a deep connection between MDS codes and super
regular matrices (and more specifically between generalized Reed-Solomon
codes, Vandermonde matrices, and Cauchy matrices). Specifically, if
$G=(I\;|\;S)$ is the generator matrix of an MDS code in systematic form, then
$S$ is a super regular matrix [RL89]. Moreover, [RL89] shows that if such a
matrix $G$ is the generator matrix of a generalized Reed-Solomon code, then
$S$ is a Cauchy matrix [RL89]. See also Remark 2.15.

####  1.1.2 Barriers

The dream for the line of work described in this paper is to give a
deterministic, $\widetilde{O}(n^{2})$-time algorithm for MMV on arbitrary
matrices. However, achieving this goal has proven to be very difficult despite
a substantial amount of work towards it. So, it is natural to ask whether
perhaps no such algorithm exists, i.e., whether MMV is in some sense _hard_.
We first show a result in this direction, and then show a barrier result to
showing SETH hardness of MMV (and even MM).444More properly, our first result
is a barrier to giving a fast algorithm for MMV, and our second result is a
barrier to showing hardness of MMV (i.e., it “gives a barrier to giving a
barrier” for a fast MMV algorithm).

##### Linear algebraic algorithms barrier.

We first prove that a natural class of deterministic linear algebraic
algorithms for MMV based on multiplying smaller matrices—including the
algorithm in Theorem 1.1—cannot run in less than $n^{\omega}$ time using when
instantiated with a matrix multiplication subroutine running in worst-case
rectangular matrix multiplication time and when performing all multiplications
independently. Specifically, the $\Omega(n^{\omega})$ lower bound holds if for
all $\alpha,\beta\geq 0$, the subroutine requires
$\Omega(n^{\omega(1,1,\alpha)})$ to compute the product of an $n\times
n^{\alpha}$ matrix and an $n\times n$, and $\Omega(n^{\omega(1,1,\beta)})$
time to compute the product of an $n\times n$ matrix and an $n\times
n^{\beta}$ matrix.

The idea is that natural algorithms for verifying that $AB=C$ for $n\times n$
matrices $A,B,C$ including ours amount to performing $k$ “zero tests.” 555Here
we describe our barrier for MMV, but in Section 3.3 we present it for the
closely related All Zeroes Problem. More specifically, the $i$th such test
checks that $L_{i}(AB-C)R_{i}=0$ for some fixed $n^{\alpha_{i}}\times n$
matrix $L_{i}$ and $n\times n^{\beta_{i}}$ matrix $R_{i}$, where
$\alpha_{i},\beta_{i}\in[0,1]$. We observe that the conditions
$L_{i}(AB-C)R_{i}=0$ for $i=1,\ldots,k$ together correspond to a homogeneous
system of $\sum_{i=1}^{k}n^{\alpha_{i}+\beta_{i}}$ linear equations in the
$n^{2}$ variables corresponding to the entries of $X=AB-C$ for $1\leq i,j\leq
n$. So, for this system to have $X_{i,j}=0$ for $1\leq i,j\leq n$ as its
unique solution, it must be the case that
$\sum_{i=1}^{k}n^{\alpha_{i}+\beta_{i}}\geq n^{2}$, which we show implies that
$\sum_{i=1}^{k}n^{\omega(1,1,\min(\alpha_{i},\beta_{i}))}\geq\sum_{i=1}^{k}n^{\omega(\alpha_{i},1,\beta_{i})}\geq
n^{\omega}$. Therefore, an algorithm that independently computes each product
$L_{i}ABR_{i}$ in time $\Omega(n^{\omega(1,1,\min(\alpha_{i},\beta_{i}))})$
uses $\Omega(n^{\omega})$ time. This barrier appears in Theorems 3.7 and 3.8.

##### A barrier to SETH-hardness of MM.

While under certain reasonable conjectures, the matrix multiplication exponent
$\omega=2$ (see [CKSU05, Conjecture 4.7 and Conjecture 3.4]), the best
provable upper bound we have is $\omega<2.371552$ by [VXXZ23]. Nevertheless,
given the apparent difficulty of showing $\omega\approx 2$, it is natural to
ask whether MM is in fact _hard_. To that end, we study showing its hardness
under the _Strong Exponential Time Hypothesis_ (SETH). However, rather than
showing SETH-hardness of MM, we show a _barrier_ to proving
$n^{\gamma}$-hardness of MM for constant $\gamma>2$ under SETH. (Because MMV
is trivially reducible to MM, our hardness barrier result also applies to
MMV.)

We informally define several concepts used in the statement of our result.
SETH says that for large constant $k$, $k$-SAT instances on $n$ variables take
nearly $2^{n}$ time to solve, and the _Nondeterministic Strong Exponential
Time Hypothesis_ (NSETH) says that certifying that such $k$-SAT formulas are
_not_ satisfiable takes nearly $2^{n}$ time even for nondeterministic
algorithms. We call a matrix _rigid_ if the Hamming distance between it and
all low-rank matrices is high (the Hamming distance and rank are quantified by
two parameters). Rigid matrices have many connections to complexity theory and
other areas, and a key goal is to find explicit, deterministic constructions
of such matrices.

Intuitively, NSETH rules out showing hardness of problems with non-trivial co-
nondeterministic algorithms under SETH. Somewhat more precisely, assuming
NSETH, problems contained in $\mathsf{coTIME}[f(n)]$ (but perhaps only known
to be in $\mathsf{TIME}[g(n)]$ for $g(n)=\omega(f(n))$), cannot be shown to be
$\Omega(f(n)^{1+\varepsilon})$-hard under SETH. (See Definition 2.22 for a
formal definition of SETH-hardness.) Künnemann [Kün18] noted that, because
Freivald’s algorithm shows that MMV is in
$\mathsf{coTIME}[n^{2}\cdot\operatorname{poly}(\log n)]$, NSETH rules out
showing $\Omega(n^{\gamma})$ hardness of MMV under SETH for constant
$\gamma>2$.

In this work, we extend this observation and give a barrier not only to
showing SETH-hardness of MMV but to showing hardness of MM. Our barrier result
says that, if there exists a constant $\gamma>2$ and a reduction from $k$-SAT
to MM such that a $O(n^{\gamma-\varepsilon})$-time algorithm for MM for any
constant $\varepsilon>0$ breaks SETH, then either (1) the _Nondeterministic
Strong Exponential Time Hypothesis_ (NSETH) is false, or (2) a new non-
randomized algorithm for computing (arbitrarily large) rigid matrices exists.
We also note that, by known results, falsifying NSETH implies a new circuit
lower bound as a consequence. In short, our barrier result says that showing
$n^{\gamma}$-hardness of MM under SETH for $\gamma>2$ would lead to major
progress on important questions in complexity theory. See Theorem 4.4 for a
formal statement.

A key idea that we use for proving our result is that it is possible to
compute the product of two _non-rigid_ matrices efficiently using a
_nondeterministic_ algorithm. This follows from two facts. First, by
definition, a non-rigid matrix is the sum of a low-rank matrix $L$ and a
sparse matrix $S$, and using nondeterminism it is possible to guess $L$ and
$S$ efficiently. Second, it is possible to compute the product of two sparse
matrices or a low-rank matrix and another matrix efficiently. (In fact, we
also use nondeterminism to guess a _rank factorization_ of $L$, and this
factorization is what allows for fast multiplication by $L$.)

Very roughly, we prove the barrier result as follows. We first suppose that
there is a reduction from $k$-SAT to (potentially multiple instances of)
matrix multiplication. In particular, such a reduction outputs several pairs
of matrices to be multiplied. We then analyze three cases:

  1. 1.

If the matrices output by this reduction always have small dimension (as a
function of $n$), then we can compute the product of each pair quickly using
standard matrix multiplication algorithms (even using naïve, cubic-time matrix
multiplication). This leads to a fast, deterministic algorithm for $k$-SAT,
which refutes SETH (and hence NSETH).

  2. 2.

If the matrices output by this reduction are always _not_ rigid, then we can
compute the product of each pair quickly using the nondeterministic algorithm
sketched above. This leads to a fast, nondeterministic algorithm for showing
that $k$-SAT formulas are not satisfiable, which refutes NSETH.

  3. 3.

Finally, if neither of the above cases holds, then the reduction must
sometimes output rigid matrices with large dimension as a function of $n$. So,
we obtain an algorithm for generating arbitrarily large rigid matrices using
an $\mathsf{NP}$ oracle: iterate through all $k$-SAT formulas $\varphi$ with
at most a given number of variables, apply the reduction from $k$-SAT to MM to
each formula, and then use the $\mathsf{NP}$ oracle to check whether each
large matrix output by the reduction is rigid.

We remark that although NSETH is a strong and not necessarily widely believed
conjecture, [JMV15, CGI+16] showed that refuting it (as in Item 2 above) would
nevertheless imply an interesting new circuit lower bound. Specifically, they
showed that if NSETH is false, then the complexity class
$\mathsf{E}^{\mathsf{NP}}$ requires series-parallel circuits of size
$\omega(n)$.

Additionally, we remark that despite how slow the “iterate through all
sufficiently large $k$-SAT formulas and apply the $k$-SAT-to-MM reduction to
each one” algorithm described in Item 3 seems, it would still substantially
improve on state-of-the-art non-randomized algorithms for generating rigid
matrices. This is also true despite the fact that the algorithm uses an
$\mathsf{NP}$ oracle. See Section 4.3 for a more thorough discussion.

####  1.1.3 Reductions

Again, motivated by the apparent challenge of fully derandomizing Freivalds’s
algorithm, we study relationships between variants of MMV with the goal of
understanding what makes the problem hard to solve deterministically in
$\widetilde{O}(n^{2})$ time but easy to solve in $\widetilde{O}(n^{2})$ time
using randomness (in contrast to MM). More specifically, we study which
variants are potentially easier than MMV (i.e., reducible to MMV, but not
obviously solvable deterministically in $\widetilde{O}(n^{2})$ time using
known techniques), equivalent to MMV, and potentially harder than MMV (i.e.,
variants to which MMV is reducible, but which are not obviously as hard as
MM). We study these questions by looking at deterministic
$\widetilde{O}(n^{2})$-time reductions between variants. See Figure 3 for a
summary of our results.

First, we show that two apparently special cases of MMV are in fact equivalent
to MMV. These special cases are: (1) the _Inverse Verification Problem_ ,
where the goal is to verify that $B=A^{-1}$ for input matrices $A$ and $B$
(equivalently, the special case of MMV where $C=I_{n}$), and (2) the
_Symmetric MMV Problem_ , where the input matrices $A$ and $B$ (but not
necessarily $C$) are symmetric. See Theorem 5.4. These reductions are
relatively simple, and complement the (also simple) reduction of [Kün18], who
showed that the All Zeroes Problem (i.e., the special case of MMV where $C=0$)
is MMV-complete (see Theorem 2.8).

Second, we identify two problems that are $\widetilde{O}(n^{2})$-time
reducible to MMV, but are not clearly solvable in $\widetilde{O}(n^{2})$ time
or equivalent to MMV. These problems are: (1) the _Strong Symmetric MMV
Problem_ , where all three of the input matrices $A$, $B$, and $C$ are
symmetric, and (2) the Monochromatic All Pairs Orthogonal Vectors Problem,
where the goal is, given vectors
$\boldsymbol{a}_{1},\ldots,\boldsymbol{a}_{n}$ to decide whether
$\langle\boldsymbol{a}_{i},\boldsymbol{a}_{j}\rangle=0$ for all $i\neq j$.

Third, we identify two problems for which there are
$\widetilde{O}(n^{2})$-time reductions from MMV and that are
$\widetilde{O}(n^{2})$-time reducible to MM. These “MMV/MM-intermediate
problems” are: (1) the Matrix Product Sparsity Problem (MPS), in which the
goal is, given matrices $A$ and $B$ and $r\geq 0$ as input, to decide whether
$\lVert AB\rVert_{0}\leq r$, and (2) the $k$-MMV problem, in which given
matrices $A_{1},\ldots,A_{k},C$ as input, the goal is to decide whether
$\prod_{i=1}^{k}A_{i}=C$. We note that MPS is equivalent to the counting
version of the Orthogonal Vectors Problem ($\\#\mathrm{OV}$).666Indeed,
Monochromatic All Pairs Orthogonal Vectors is no harder than MMV (and not
obviously equivalent), Bichromatic All Pairs Orthogonal Vectors is equivalent
to the All Zeroes Problem and is therefore equivalent to MMV, and
MPS/$\\#\mathrm{OV}$ is at least as hard as MMV. In the fine-grained
complexity setting OV variants are usually considered with $n$ vectors in
dimension $d=\operatorname{poly}(\log n)$; here we are considering the regime
where $d=n$. We additionally show that $k$-MMV is equivalent to the $k$-All
Zeroes problem, i.e., $k$-MMV where $C$ is fixed to be $0$.

###  1.2 Related Work

We next discuss other algorithms for MMV and related problems on $n\times n$
integer matrices $A$, $B$, and $C$. We summarize these algorithms, as well as
ours, in Table 1. We start by noting that it suffices to consider the special
case of MMV where $C=0$ (i.e., where the goal is to decide whether $AB=0$),
which is called the All Zeroes Problem. Indeed, a result from [Kün18] (which
we include as Theorem 2.8) shows that there is a simple $O(n^{2})$-time
reduction from MMV on $n\times n$ matrices $A,B,C$ to the All Zeroes problem
on $2n\times 2n$ matrices $A^{\prime},B^{\prime}$ with the property that
$\lVert AB-C\rVert_{0}=\lVert A^{\prime}B^{\prime}\rVert_{0}$. So, for this
section we consider the All Zeroes Problem without loss of generality.

Perhaps the most closely related works to ours are [IS09, ABFK23], which use
fast rectangular matrix multiplication for the _Output-Sensitive Matrix
Multiplication Problem_ (OSMM). In $t$-OSMM, the goal is, given matrices $A,B$
as input, to compute the product $AB$ when it is promised to be $t$-sparse.
There is a trivial reduction from MMV when the output is promised to be
$t$-sparse to $t$-OSMM—compute $AB$ and check whether it is equal to $0$.
Indeed, OSMM is essentially the search version of sparse MMV. However, it is
not clear that the measurement matrix $M$ in [IS09] is deterministically
computable in $\widetilde{O}(n^{2})$ time, and so the algorithm in [IS09] is a
non-uniform algorithm as described. There are other candidate measurement
matrices with deterministic constructions that may work for a similar purpose
[Iwe23], but the exact tradeoffs do not seem to have been analyzed and it is
not clear that it is possible to get a (uniform) algorithm with the same
parameters. Additionally, [IS09] only handles the case when all columns or
rows of $AB$ are promised to have a given sparsity, rather than the case where
there is a “global bound” of $t$ on the sparsity of the matrix product itself.

The main algorithm in [ABFK23] for OSMM (summarized in [ABFK23, Theorem 1.4])
runs in randomized time $O(n^{1.3459\delta})$ when both the input matrices
$A,B$ and their product $AB$ are $n^{\delta}$-sparse.777A more general version
of this theorem, which gives an algorithm whose running time depends both on
the sparsity of the input matrices $A,B$ and of their product $AB$, appears as
[ABFK23, Theorem 1.7]. We note that [ABFK23] was written independently and
concurrently with this work.

Besides simply using matrix multiplication, perhaps the most natural idea for
an algorithm for the All Zeroes problem is to compute a random entry
$(AB)_{i,j}$ of $AB$ and check whether it is non-zero. If $\lVert
AB\rVert_{0}\geq n^{\delta}$, then sampling, say, $10n^{2-\delta}$ random
entries of $AB$ independently will find a non-zero entry with good constant
probability. Because computing each such entry amounts to computing an inner
product, and sampling indices $i,j\sim\\{{1,\ldots,n}\\}$ takes roughly
$2\log_{2}n$ random bits, this algorithm overall takes
$\widetilde{O}(n^{3-\delta})$ time and $O(n^{2-\delta}\log n)$ random bits.
So, this algorithm is relatively efficient and succeeds with good probability
in the case when $AB$ is dense, but even then requires a relatively large
number of random bits. We also note the somewhat odd fact that this algorithm
is most efficient when $AB$ is dense, whereas our algorithms are most
efficient when $AB$ is sparse.

Freivalds’s algorithm [Fre79] works by sampling a uniformly random vector
$\boldsymbol{x}\sim\\{{0,1}\\}^{n}$, and outputting “YES” if
$AB\boldsymbol{x}=\boldsymbol{0}$ and “NO” otherwise. If $AB=0$, then this
algorithm is always correct, and if $AB\neq 0$ then it fails with probability
at most $1/2$.888To see this, note that in the latter case some row
$\boldsymbol{s}^{T}$ of $AB$ must be non-zero, and let $j^{*}$ be the index of
the last non-zero entry in $\boldsymbol{s}$. Then for uniformly random
$\boldsymbol{x}\sim\\{{0,1}\\}^{n}$,
$\Pr[AB\boldsymbol{x}=\boldsymbol{0}]\leq\Pr[\langle\boldsymbol{s},\boldsymbol{x}\rangle=0]=\Pr[s_{j^{*}}x_{j^{*}}=-\sum_{k=1}^{j^{*}-1}s_{k}x_{k}]\leq
1/2$. Moreover, this holds for matrices $A,B$ over any integral domain $R$
with a multiplicative identity $1$, and so Freivalds’s algorithm works for MMV
over all such $R$. In particular, Freivalds’s algorithm has one-sided error
with no false negatives (i.e., it is a $\mathsf{coRP}$ algorithm).

A key idea for subsequent algorithms was to reduce MMV to a question about
polynomials. The main idea is the following. Define
$\boldsymbol{x}:=(1,x,x^{2},\ldots,x^{n-1})^{T}$, where $x$ is an
indeterminate, and define
$p_{i}(x):=(AB\boldsymbol{x})_{i}=\sum_{j=1}^{n}(AB)_{i,j}\cdot x^{j-1}$. Note
that $AB=0$ if and only if the polynomials $p_{i}(x)$ are identically zero (as
formal polynomials) for all $i\in\\{{1,\ldots,n}\\}$. Furthermore, if the
$i$th row of $AB$ is non-zero then $p_{i}(x)$ is a non-zero polynomial of
degree at most $n-1$, and therefore has at most $n-1$ distinct complex (and
hence integral) roots. So, for such $p_{i}(x)$ and a non-empty set
$S\subset\mathbb{Z}$, $\Pr_{\alpha\sim
S}[p(\alpha)=0]\leq(n-1)/\left|{S}\right|$, which is less than $1/2$ when
$\left|{S}\right|\geq 2n$. This observation leads to the following algorithm
for MMV, which forms the basis for Kimbrel and Sinha’s algorithm [KS93].
Sample $\alpha\sim\\{{1,\ldots,2n}\\}$, and output “YES” if and only if
$AB\boldsymbol{\alpha}=\boldsymbol{0}$ for
$\boldsymbol{\alpha}:=(1,\alpha,\alpha^{2},\ldots,\alpha^{n-1})^{T}$. Using
associativity, it is possible to compute this product as
$A(B\boldsymbol{\alpha})$ using $O(n^{2})$ arithmetic operations.

However, there is an issue with this algorithm: it requires computing powers
of $\alpha$ up to $\alpha^{n-1}$. These powers require $\Omega(n)$ bits to
represent for any integer $\alpha\geq 2$, and so performing arithmetic
operations with them takes $\Omega(n)$ time. To solve this, Kimbrel and Sinha
instead consider the “test vector” $\boldsymbol{\alpha}$ modulo an (arbitrary)
prime $2n\leq q\leq 4n$, which they can find deterministically in $O(n^{2})$
time. They show that their algorithm is still correct with good probability
(over the choice of $\alpha$) with this modification.

Korec and Wiedermann [KW14] showed how to _deterministically_ find a good
$\alpha$ for the above test—that is, a value $\alpha$ such that
$p_{i}(\alpha)\neq 0$ if $p_{i}$ is not identically zero—using _Cauchy’s
bound_ , which gives an upper bound on the magnitude of the largest root of a
polynomial as a function of the polynomial’s coefficients. Namely, they just
choose $\alpha$ larger than Cauchy’s bound. (They note that the maximum
magnitude of an entry in $AB$—and hence of a coefficient in any of the
polynomials $p_{i}(x)$—is at most $n\mu^{2}$, where $\mu$ is the maximum
magnitude of an entry in $A$ or $B$.) Their algorithm uses only $O(n^{2})$
arithmetic operations, but again requires computing powers of $\alpha$ up to
$\alpha^{n-1}$, and therefore the algorithm has bit complexity
$\Omega(n^{3})$.

Additionally, we mention the work of Künnemann [Kün18], which works for MMV
over finite fields $\mathbb{F}_{q}$ with $q>n^{2}$ (he reduces MMV over the
integers to MMV over such fields). His algorithm works by considering the
bivariate polynomial $f(x,y)=f_{A,B}(x,y):=\boldsymbol{x}^{T}AB\boldsymbol{y}$
for $\boldsymbol{x}=(1,x,x^{2},\ldots,x^{n-1})$,
$\boldsymbol{y}=(1,y,y^{2},\ldots,y^{n-1})$, where $x$ and $y$ are
indeterminates, and the corresponding univariate polynomial
$g(x)=g_{A,B}(x):=f(x,x^{n})$. The coefficient of $x^{(i-1)+(j-1)n}$ in $g(x)$
(and of $x^{i-1}y^{j-1}$ in $f(x,y)$) is equal to $(AB)_{i,j}$, and so to
decide whether $AB=0$ it suffices to decide whether $g(x)$ (or $f(x,y)$) is
identically zero as a formal polynomial.999Indeed, [Kün18] notes that this
mapping from $A,B$ to $g(x)$ is a reduction from the All Zeroes Problem to
Univariate Polynomial Identity Testing (UPIT). He shows that to do this it in
turn suffices to decide whether $g(\alpha^{i})=0$ for all
$i\in\\{{0,\ldots,t-1}\\}$, where $\alpha\in\mathbb{F}_{q}$ is an element of
order at least $n^{2}$ and $t=n^{\delta}$ is an upper bound on the sparsity of
$AB$. Indeed, he notes that the system of equations
$g(1)=\cdots=g(\alpha^{t-1})=0$ is a Vandermonde system of homogeneous linear
equations in the at most $t$ non-zero entries $(AB)_{i,j}$ in $AB$, and so its
only solution is the solution $(AB)_{i,j}=0$ for all $1\leq i,j\leq n$ (i.e.,
it must be the case that $AB=0$). To evaluate $g$ on the $t$ values
$1,\alpha,\ldots,\alpha^{t-1}$ quickly, he uses a known result about fast
multipoint polynomial evaluation.

We also note that MMV and its variants have also been studied from angles
other than derandomization of Freivalds’s algorithm. Notably, [BS04] gave a
_quantum_ $O(n^{5/3})$-time algorithm for MMV, [HTW23] studied the _Boolean_
Matrix Multiplication Verification problem, and [GLL+17, WW23] study the
problem of _correcting_ matrix products. I.e., they study the problem of
_computing_ $AB$ given matrices $A$, $B$, and $C$ where $\lVert
AB-C\rVert_{0}$ is guaranteed to be small, which Künnemann showed is
equivalent to OSMM.

Finally, we remark that other recent works including [CGI+16, BGK+23, ABB+23,
BKM+23] have studied “barriers to SETH hardness” akin to Theorem 4.4.

###  1.3 Open Questions

Of course, the main question that we leave open is whether Freivalds’s
algorithm can be fully derandomized, i.e., whether there is a deterministic
$\widetilde{O}(n^{2})$-time algorithm for MMV on $n\times n$ matrices over
finite fields $\mathbb{F}_{q}$ with $q\leq\operatorname{poly}(n)$ and integer
matrices with entries $[-n^{c},n^{c}]$ for constant $c>0$. Giving such an
algorithm for a natural special case of MMV (such as those described in
Section 5.2) also seems like a natural step in this direction. Additionally,
it would be interesting to extend our results for MMV in the sparse regime to
Output Sensitive Matrix Multiplication. The coding-theoretic techniques that
we use seem amenable to this.

###  1.4 Acknowledgments

We thank Amir Nayyeri for many helpful discussions in the early stages of work
on this paper, and Mark Iwen [Iwe23] for answering questions about [IS09].

##  2 Preliminaries

We define $\lVert\boldsymbol{v}\rVert_{0}$ (respectively, $\lVert
M\rVert_{0}$) to be the number of non-zero entries (i.e., Hamming weight) in a
vector $\boldsymbol{v}$ (respectively, matrix $M$). We call a vector
$\boldsymbol{v}$ (respectively, matrix $M$) _$t$ -sparse_ if
$\lVert\boldsymbol{v}\rVert_{0}\leq t$ (respectively, if $\lVert
M\rVert_{0}\leq t$).

###  2.1 Matrix Multiplication

We first give definitions related to matrix multiplication.

######  Definition 2.1 ($\textrm{MM}_{R}$).

The Matrix Multiplication Problem over a ring $R$ ($\textrm{MM}_{R}$) is
defined as follows. Given matrices $A,B\in R^{n\times n}$ for some
$n\in\mathbb{Z}^{+}$, compute their product $AB$.

######  Definition 2.2 (Rectangular and Square Matrix Multiplication
Exponents).

For $\alpha,\beta,\gamma\in[0,1]$, we define the _rectangular matrix
multiplication exponent_ $\omega(\alpha,\beta,\gamma)$ to be the infimum over
$\omega^{\prime}>0$ such that the product of an $n^{\alpha}\times n^{\beta}$
matrix $A$ and an $n^{\beta}\times n^{\gamma}$ matrix $B$ can be computed
using $O(n^{\omega^{\prime}})$ arithmetic operations. We also define the
(square) _matrix multiplication exponent_ as $\omega:=\omega(1,1,1)$.

Additionally, we define the _dual matrix multiplication exponent_
$\omega^{\perp}$ as

$\omega^{\perp}:=\sup\\{{\omega^{\prime}>0:\omega(1,1,\omega^{\prime})=2}\\}\
\text{.}$ (1)

A recent line of work [LU18, AV21, DWZ23, LG23, VXXZ23] has shown improved
bounds on rectangular matrix multiplication exponents $\omega(1,1,\beta)$
(including $\omega=\omega(1,1,1)$) and the dual matrix multiplication exponent
$\omega^{\perp}$. The current best bounds for all of these
quantities—including, to the best of our knowledge, $\omega(1,1,\beta)$ for
all $\beta\in(\omega^{\perp},1]$—appear in [VXXZ23]. In particular, [VXXZ23]
proves the following bounds:

$\displaystyle\omega$ $\displaystyle\leq 2.371552\ \text{,}$ (2)
$\displaystyle\omega^{\perp}$ $\displaystyle\geq 0.321334\ \text{.}$ (3)

We will use the following upper bound on rectangular matrix multiplication
exponents $\omega(1,1,\beta)$ in terms of $\beta$, $\omega$, and
$\omega^{\perp}$.

######  Theorem 2.3 ([LR83, LG12]).

Let $\beta\in[0,1]$. Then

$\omega(1,1,\beta)\leq\begin{cases}2&\text{if $0\leq\beta\leq\omega^{\perp}$
,}\\\ 2+(\omega-2)\cdot\dfrac{\beta-\omega^{\perp}}{1-\omega^{\perp}}&\text{if
$\omega^{\perp}<\beta\leq 1$ .}\end{cases}$

We note that the second case of Theorem 2.3 implies that if $\omega>2$ then
$\omega(1,1,\beta)<\omega$ for $\beta<1$. We will also use the following lower
bound on rectangular matrix multiplication exponents.

######  Lemma 2.4.

For any $\alpha,\beta\in[0,1]$,
$\omega(\alpha,1,\beta)\geq\omega-2+\alpha+\beta$.

###### Proof.

Consider two matrices $X,Y\in R^{n\times n}$ over some ring $R$. Partition $X$
into $\lceil n^{1-\alpha}\rceil$ submatrices with dimensions $\lceil
n^{\alpha}\rceil\times n$, and $Y$ into $\lceil n^{1-\beta}\rceil$ submatrices
with dimensions $n\times\lceil n^{\beta}\rceil$ (padding $X$ and $Y$ with
zeroes if $\lceil n^{\alpha}\rceil$ or $\lceil n^{\beta}\rceil$ does not
divide $n$).

Then for any constant $\varepsilon>0$, the product $XY$ can be computed using
$O(\lceil n^{1-\alpha}\rceil\cdot\lceil n^{1-\beta}\rceil\cdot
n^{\omega(\alpha,1,\beta)+\varepsilon})=O(n^{2+\omega(\alpha,1,\beta)-\alpha-\beta+\varepsilon})$
algebraic operations by multiplying each of the $O(n^{1-\alpha}\cdot
n^{1-\beta})=O(n^{2-\alpha-\beta})$ pairs of submatrices $X^{\prime}$ of $X$
and $Y^{\prime}$ of $Y$ in time $O(n^{\omega(\alpha,1,\beta)+\varepsilon})$.
It follows that $\omega\leq 2+\omega(\alpha,1,\beta)-\alpha-\beta$, and the
result follows by rearranging. ∎

Finally, we will also use the following fact about equivalences among
rectangular matrix multiplication exponents.

######  Theorem 2.5 ([LR83]).

For any $\beta\in[0,1]$,
$\omega(1,1,\beta)=\omega(1,\beta,1)=\omega(\beta,1,1)$.

###  2.2 Matrix Multiplication Verification

We next define Matrix Multiplication Verification and the All Zeroes Problem
over arbitrary rings $R$ and with a sparsity parameter $t$.

######  Definition 2.6 ($\textrm{MMV}_{R}^{t}$).

The Matrix Multiplication Verification Problem over a ring $R$ with sparsity
parameter $t=t(n)\geq 0$ ($\textrm{MMV}_{R}^{t}$) is defined as follows. Given
matrices $A,B,C\in R^{n\times n}$ for some $n\in\mathbb{Z}^{+}$ such that
$\lVert AB-C\rVert_{0}\leq t$ as input, decide whether $AB=C$.

######  Definition 2.7 ($\textrm{AllZeroes}_{R}^{t}$).

The All Zeroes Problem over a ring $R$ with sparsity parameter $t=t(n)\geq 0$
($\textrm{AllZeroes}_{R}^{t}$) is defined as follows. Given matrices $A,B\in
R^{n\times n}$ for some $n\in\mathbb{Z}^{+}$ such that $\lVert
AB\rVert_{0}\leq t$ as input, decide whether $AB=0$.

We note that when $t\geq n^{2}$, $t$ does not restrict the input.

We use the following reduction from [Kün18] with the additional observation
that it is sparsity-preserving. We provide its simple proof for completeness.

######  Theorem 2.8 ([Kün18, Proposition 3.1]).

For all $n\in\mathbb{Z}^{+}$ and $0\leq t\leq n^{2}$, there is a reduction
from $\textrm{MMV}_{R}^{t}$ on $n\times n$ matrices to
$\textrm{AllZeroes}_{R}^{t}$ on $2n\times 2n$ matrices that uses $O(n^{2})$
arithmetic operations on $R$.

###### Proof.

Let the matrices $A,B,C$ be an instance of MMV, and define

$A^{\prime}:=\begin{bmatrix}A&-I\\\ 0&0\\\ \end{bmatrix}\ \text{,}\quad
B^{\prime}:=\begin{bmatrix}B&0\\\ C&0\\\ \end{bmatrix}\ \text{.}$

We then have that

$A^{\prime}B^{\prime}=\begin{bmatrix}A&-I\\\ 0&0\\\
\end{bmatrix}\cdot\begin{bmatrix}B&0\\\ C&0\\\
\end{bmatrix}=\begin{bmatrix}AB-C&0\\\ 0&0\\\ \end{bmatrix}\ \text{,}$

and therefore that $\lVert A^{\prime}B^{\prime}\rVert_{0}=\lVert
AB-C\rVert_{0}$. It follows that $A^{\prime},B^{\prime}$ is a YES instance of
$\textrm{AllZeroes}_{R}^{t}$ if and only if $A,B,C$ is a YES instance of
$\textrm{MMV}_{R}^{t}$, as needed. ∎

###  2.3 Coding Theory

We next review useful background information about (linear) error-correcting
codes $\mathcal{C}\subseteq\mathbb{F}_{q}^{n}$. We refer the reader to [GRS22]
for a comprehensive resource on coding theory. We start by giving a “dual”
definition of error-correcting codes in terms of parity-check matrices $H$,
which will be useful for our work.

######  Definition 2.9.

Let $k\geq 0$ and $n\geq 1$ be integers satisfying $k\leq n$, let $q$ be a
prime power, and let $H\in\mathbb{F}_{q}^{(n-k)\times n}$ be a matrix with
linearly independent rows. Then

$\mathcal{C}=\mathcal{C}^{\perp}(H):=\\{{\boldsymbol{x}\in\mathbb{F}_{q}^{n}:H\boldsymbol{x}=\boldsymbol{0}}\\}$

is the linear error-correcting code with parity check matrix $H$.

We remark that it is also possible to define a code in the primal way using a
_generator matrix_ $G\in\mathbb{F}_{q}^{k\times n}$, setting

$\mathcal{C}=\mathcal{C}(G)=\\{{G^{T}\boldsymbol{x}:\boldsymbol{x}\in\mathbb{F}_{q}^{k}}\\}\
\text{.}$

That is, $\mathcal{C}(G)$ is the linear subspace of $\mathbb{F}_{q}^{n}$
spanned by rows of $G$. A generator matrix of the form
$G=(I_{k}\;|\;G^{\prime})$ is said to be in _systematic form_. Although we do
not directly need this definition, it is related to a deep connection between
coding theory and matrices with the “regularity” property we need for Theorem
1.2; see Remark 2.15.

The _minimum distance_ of a linear code $\mathcal{C}$ is defined as

$d=d(\mathcal{C}):=\min_{\begin{subarray}{c}\boldsymbol{x},\boldsymbol{y}\in\mathcal{C},\\\
\boldsymbol{x}\neq\boldsymbol{y}\end{subarray}}\lVert\boldsymbol{x}-\boldsymbol{y}\rVert_{0}=\min_{\boldsymbol{x}\in\mathcal{C}\setminus\\{{\boldsymbol{0}}\\}}\lVert\boldsymbol{x}\rVert_{0}\
\text{.}$

Note that for any $\mathcal{C}\subseteq\mathbb{F}_{q}^{n}$, $0\leq
d(\mathcal{C})\leq n$.

A linear error-correcting code $\mathcal{C}$ with parity-check matrix
$H\in\mathbb{F}_{q}^{(n-k)\times n}$ and minimum distance $d=d(\mathcal{C})$
is called a $[n,k,d]_{q}$ code. Here $n$ is the _block length_ of the code and
$k$ is the _dimension_ of the code.

A primary goal of coding theory is to study the largest values of $k=k(n)$ and
$d=d(n)$ for which $[n,k,d]_{q}$ codes exist (either for constant $q$ or a
family of values $q=q(n)$). A fundamental result in coding theory called the
_Singleton bound_ asserts that for any $[n,k,d]_{q}$ code,

$d\leq n-k+1\ \text{.}$ (4)

See, e.g., [GRS22, Theorem 4.3.1]. A code $\mathcal{C}$ for which the
preceding inequality is tight (i.e., for which $d=n-k+1$) is called a _maximum
distance separable (MDS)_ code. We will use the fact that MDS codes exist for
a wide range of values of $k$ and $n$, and moreover that these codes have
efficiently computable parity check matrices $H=H(k,n)$. In particular,
generalized Reed-Solomon (GRS) codes are a family of such MDS codes (see [Hal,
Theorem 5.1.1] and [GRS22, Claim 5.2.3]).

######  Theorem 2.10 ([Hal, Theorem 5.1.1]).

Let $q$ be a prime power, and let $k$ and $n$ be integers satisfying $0<k\leq
n\leq q$. Then there exists a $[k,n,n-k+1]_{q}$ code $\mathcal{C}$. Moreover,
there exists an algorithm to compute a parity check matrix
$H=H(k,n)\in\mathbb{F}_{q}^{(n-k)\times n}$ of such a code $\mathcal{C}$ in
$n(n-k)\cdot\operatorname{poly}(\log q)$ time.

We remark that the parity-check matrix $H$ has $(n-k)\cdot n$ entries, and so
the preceding theorem says that $H$ is computable in $\operatorname{poly}(\log
q)$ time per entry. For GRS codes, $H$ is the transpose of a Vandermonde
matrix. Such matrices are defined as follows.

######  Definition 2.11 (Vandermonde Matrix).

Let $m$ and $n$ be positive integers. Let $x_{1},\ldots,x_{n}\in\mathbb{F}$ be
distinct elements of a field $\mathbb{F}$. A _Vandermonde matrix_
$V\in\mathbb{F}^{n\times m}$ is a matrix with $V_{i,j}:=x_{i}^{j-1}$ for
distinct elements $x_{1},\ldots,x_{n}\in\mathbb{F}$. I.e., $V$ has the
following form:

$\begin{bmatrix}1&x_{1}&x_{1}^{2}&\cdots&x_{1}^{m-1}\\\
1&x_{2}&x_{2}^{2}&\cdots&x_{2}^{m-1}\\\ \vdots&\vdots&\vdots&\ddots&\vdots\\\
1&x_{n}&x_{n}^{2}&\cdots&x_{n}^{m-1}\end{bmatrix}\ \text{.}$

As a consequence of Theorem 2.10, the definition of minimum distance, and the
definition of a parity check matrix we get the following corollary. In
particular, the corollary uses the fact that if $H$ is a parity check matrix
for a code with minimum distance $d$ then no non-zero vector $\boldsymbol{x}$
with $\lVert\boldsymbol{x}\rVert_{0}<d$ can be such that
$H\boldsymbol{x}=\boldsymbol{0}$.

######  Corollary 2.12.

Let $q$ be a prime power, and let $k$ and $n$ be integers satisfying $0<k\leq
n\leq q$. Then there exists a deterministic algorithm that runs in
$n(n-k)\cdot\operatorname{poly}(\log q)$ time for computing a matrix
$H\in\mathbb{F}_{q}^{(n-k)\times n}$ such that for all non-zero
$\boldsymbol{x}\in\mathbb{F}_{q}^{n}$ with $\lVert\boldsymbol{x}\rVert_{0}\leq
n-k$, $H\boldsymbol{x}\neq\boldsymbol{0}$.

We note that if $q\leq\operatorname{poly}(n)$ then the algorithm in Corollary
2.12 runs in $\widetilde{O}(n^{2})$ time. We also again emphasize that by the
Singleton bound (Equation 4) the parameters in Corollary 2.12 are optimal in
terms of the trade-off between between $k$ and $d$ for fixed $n$.

###  2.4 Regular and Super Regular Matrices

We next define and discuss regular matrices.

######  Definition 2.13 (Regular Matrix).

Let $\mathbb{F}$ be a field and $k\in\mathbb{Z}^{+}$. A matrix
$S\in\mathbb{F}^{n\times m}$ is _$k$ -regular_ matrix, if all of its $k\times
k$ submatrices are non-singular. $A$ is _super regular_ , if it is $k$-regular
for every $1\leq k\leq\min(n,m)$.

We will use the following simple construction of super regular matrices.

######  Definition 2.14 (Cauchy Matrix).

Let $q$ be a prime power, $n$ and $k$ be positive integers satisfying $k+n\geq
q$, and $x_{1},\ldots,x_{n},y_{1},\ldots,y_{k}$ be distinct elements of
$\mathbb{F}_{q}$. Then $S\in\mathbb{F}_{q}^{n\times k}$ defined by
$S_{i,j}=1/(x_{i}-y_{j})$ is a _Cauchy matrix_.

######  Remark 2.15.

We again recall the correspondence between MDS codes and super regular
matrices: a matrix $G=(I_{k}\;|\;S)\in\mathbb{F}_{q}^{k\times n}$ is a
generator matrix of an MDS code if and only if $G^{\prime}$ is super regular
[RL89]. In fact, as [RL89] shows, it turns out that
$G=(I_{k}\;|\;S)\in\mathbb{F}_{q}^{k\times n}$ is the generator matrix of a
generalized Reed-Solomon (GRS) code if and only if $S$ is a Cauchy matrix!
Indeed, this illustrates a close relationship between GRS codes, Vandermonde
matrices (which are generator matrices of GRS codes not in systematic form),
and Cauchy matrices (which correspond to the “non-identity part” of generator
matrices of GRS codes in systematic form).

For completeness, we include a proof that Cauchy matrices are super regular.

######  Proposition 2.16.

Let $q$ be a prime power, $n$ and $k$ be positive integers satisfying $k+n\geq
q$, and $S\in\mathbb{F}_{q}^{n\times k}$ be a Cauchy matrix. Then $S$ is super
regular.

###### Proof.

For $1\leq m\leq\min(n,k)$, consider an arbitrary submatrix
$S^{\prime}\in\mathbb{F}_{q}^{m\times m}$ of $S$. Note that $S^{\prime}$ is a
Cauchy matrix, too, and
$S^{\prime}=(1/(x^{\prime}_{i}-y^{\prime}_{j}))_{i,j=1}^{m}$ for distinct
$x^{\prime}_{1},\ldots x^{\prime}_{m},y^{\prime}_{1},\ldots,y^{\prime}_{m}$.
The determinant of $S^{\prime}$, known as the Cauchy determinant [PS72, Part
VII, Chapter 1, Problem 3], is

$\det(S^{\prime})=\frac{\prod_{i=2}^{m}\prod_{j=1}^{i-1}(x^{\prime}_{i}-x^{\prime}_{j})(y^{\prime}_{i}-y^{\prime}_{j})}{\prod_{i=1}^{m}\prod_{j=1}^{m}(x^{\prime}_{i}-y^{\prime}_{j})}\;.$

Since
$x^{\prime}_{1},\ldots,x^{\prime}_{n},y^{\prime}_{1},\ldots,y^{\prime}_{k}$
are distinct, $\det(S^{\prime})\neq 0$, which finishes the proof. ∎

As a consequence of Proposition 2.16, we get an efficient construction of
(columns of) super regular matrices.

######  Corollary 2.17.

Let $q$ be a prime power, and let $n$, $k$, and $i$ be positive integers
satisfying $k+n\geq q$ and $1\leq i\leq k$. Then there exists a deterministic
algorithm that runs in time $n\cdot\operatorname{poly}(\log q,\log n)$, and on
input $(q,n,k,i)$ outputs the $i$th column $\boldsymbol{c}_{i}$ of a super
regular matrix
$S=(\boldsymbol{c}_{1},\ldots,\boldsymbol{c}_{k})\in\mathbb{F}_{q}^{n\times
k}$.

###  2.5 Fine-Grained Complexity

In the $k$-SAT problem, given a $k$-CNF formula $\varphi$, the task is to
check if $\varphi$ has a satisfying assignment. The complement of $k$-SAT, the
$k$-TAUT problem, is to decide if all assignments to the variables of a given
$k$-DNF formula satisfy it. The celebrated Strong Exponential Time Hypothesis
(SETH) is now central to the field of fine-grained complexity.

######  Definition 2.18 (Strong Exponential Time Hypothesis (SETH), [IP99]).

For every constant $\varepsilon>0$ there exists $k\in\mathbb{Z}^{+}$ such that
no deterministic algorithm solves $k$-SAT on formulas with $n$ variables in
time $2^{(1-\varepsilon)n}$.

The field of fine-grained complexity has leveraged SETH to prove tight bounds
on the complexity of a large host of problems (see the excellent surveys by
Vassilevska Williams [Vas15, Vas18]). We will also use the following stronger
hypothesis.

######  Definition 2.19 (Nondeterministic Strong Exponential Time Hypothesis
(NSETH), [CGI+16]).

For every constant $\varepsilon>0$ there exists $k\in\mathbb{Z}^{+}$ such that
no nondeterministic algorithm solves $k$-TAUT on formulas with $n$ variables
in time $2^{(1-\varepsilon)n}$.

A classical tool used in studies of algorithms for $k$-SAT is the
Sparsification Lemma.

######  Theorem 2.20 (Sparsification Lemma [IPZ98]).

For every $k\geq 3$ and $\lambda>0$ there exists a constant $c=c(k,\gamma)$
such that every $k$-SAT formula $\varphi$ with $n$ variables can be expressed
as $\varphi=\lor_{i=1}^{r}\psi_{i}$ where $r\leq 2^{\lambda n}$ and each
$\psi_{i}$ is a $k$-SAT formula with at most $cn$ clauses. Moreover, all
$\psi_{i}$ can be computed in $2^{\lambda n}$-time.

Now we formally define the notions of fine-grained reductions and SETH-
hardness. We start with the definition of fine-grained reductions from [Vas15,
Definition 6] with a small modification that specifies the dependence of
$\delta$ on $\varepsilon$.

######  Definition 2.21 (Fine-grained reductions).

Let $P,Q$ be problems, $p,q\colon\mathbb{Z}_{\geq 0}\to\mathbb{Z}_{\geq 0}$ be
non-decreasing functions and
${\delta\colon\mathbb{R}_{>0}\to\mathbb{R}_{>0}}$. We say that $(P,p(n))$
_$\delta$ -fine-grained reduces_ to $(Q,q(n))$ and write
$(P,p(n))\leq_{\delta}(Q,q(n))$, if for every $\varepsilon>0$ and
$\delta=\delta(\varepsilon)>0$, there exists an algorithm $\mathcal{A}$ for
$P$ with oracle access to $Q$, a constant $d$, a function
$t(n)\colon\mathbb{Z}_{\geq 0}\to\mathbb{Z}_{\geq 0}$, such that on any
instance of $P$ of size $n$, the algorithm $\mathcal{A}$

  * •

runs in time at most $d(p(n))^{1-\delta}$;

  * •

produces at most $t(n)$ instances of $Q$ adaptively: every instance depends on
the previously produced instances as well as the answers of the oracle $Q$;

  * •

the sizes $n_{i}$ of the produced instances satisfy the inequality

$\sum_{i=1}^{t(n)}q(n_{i})^{1-\varepsilon}\leq d(p(n))^{1-\delta}\,.$

It is easy to see that if $(P,p(n))\leq_{\delta}(Q,q(n))$, then for every
$\varepsilon>0$, an algorithm for $Q$ running in time
$O(q(n)^{1-\varepsilon})$ implies an algorithm for $P$ running in time
$O(p(n)^{1-\delta})$. Equipped with this definition, we are ready to define
SETH-hardness of a problem. SETH-hardness of a problem is a sequence of fine-
grained reductions from $k$-SAT for every value of $k$.

######  Definition 2.22 (SETH-hardness).

Let $p\colon\mathbb{Z}_{\geq 0}\to\mathbb{Z}_{\geq 0}$ be a non-decreasing
function. We say that a problem $P$ is _$p(n)$ -SETH-hard_ if there exists a
function $\delta\colon\mathbb{R}_{>0}\to\mathbb{R}_{>0}$ and for every
$k\in\mathbb{N}$,

$(k\text{-SAT},2^{n})\leq_{\delta}(P,p(n))\,.$

It is now easy to see that if a problem $P$ is $p(n)$-SETH-hard, then any
algorithm solving $P$ in time $p(n)^{(1-\varepsilon)}$ implies an algorithm
solving $k$-SAT in time $2^{(1-\delta(\varepsilon))n}$ for all $k$, thus,
breaking SETH.

###  2.6 Matrix Rigidity and Circuit Lower Bounds

A celebrated result of Valiant [Val77] from 1977 shows that all linear
functions computed by linear circuits of logarithmic depth and linear size can
be written as a sum of a sparse and low-rank matrices. Valiant therefore
introduced the notion of _rigid_ matrices.

######  Definition 2.23.

Let $\mathbb{F}$ be a field, $A\in\mathbb{F}^{n\times n}$ be a matrix, and
$0\leq r\leq n$. The rigidity of $A$ over $\mathbb{F}$, denoted by
${\mathcal{R}}_{r}^{\mathbb{F}}(A)$, is the Hamming distance between $A$ and
the set of matrices of rank at most $r$. Formally,

${\mathcal{R}}_{r}^{\mathbb{F}}(A):=\min_{S\colon\operatorname{rank}(A-S)\leq
r}\|S\|_{0}\;.$

In other words, a matrix $A$ has rigidity
${\mathcal{R}}_{r}^{\mathbb{F}}(A)\geq s$ if and only if
$A\in\mathbb{F}^{n\times n}$ _cannot_ be written as a sum

$A=S+L\;,$

where $S\in\mathbb{F}^{n\times n}$ is an $(s-1)$-sparse matrix, and
$L\in\mathbb{F}^{n\times n}$ has low rank $\operatorname{rank}(L)\leq r$.

Valiant proved that computing a matrix $A\in\mathbb{F}^{n\times n}$ of
rigidity ${\mathcal{R}}_{\varepsilon n}^{\mathbb{F}}(A)\geq n^{1+\varepsilon}$
for a constant $\varepsilon$, requires linear circuits of super-linear size
and logarithmic depth. The construction of a rigid matrix even in the
complexity class $\mathsf{E}^{\mathsf{NP}}$ (i.e., an
$\mathsf{E}^{\mathsf{NP}}$ algorithm that outputs rigid matrices) would give
us a long-awaited super-linear circuit lower bound.

##  3 Fast Matrix Multiplication Verification for Sparse Matrices

In this section, we prove the main algorithmic results of this work: we
present efficient deterministic and randomized algorithms for sparse MMV over
the integers and finite fields. Specifically, in Sections 3.1 and 3.2, we
prove Theorems 1.1 and 1.2, respectively. In Section 3.3, we give a simple
barrier to extending these techniques to the general case of MMV.

###  3.1 Deterministic MMV for Sparse Matrices

We present a deterministic algorithm that solves MMV over the ring of
integers. We do this by first giving an algorithm that solves MMV over finite
fields in Theorem 3.2, and then extend this result to the ring of integers in
Corollary 3.3.

We will use the following simple observation relating the sparsity of a matrix
with the sparsity of its rows and columns. This observation also appears,
e.g., in [WW23].

######  Lemma 3.1.

Let $M$ be a $t$-sparse matrix. Then $M$ has a non-zero, $\sqrt{t}$-sparse row
or column.

###### Proof.

If $M$ has a non-zero, $\sqrt{t}$-sparse row then the claim holds. So, suppose
that all non-zero rows of $M$ have more than $\sqrt{t}$ non-zero entries.
Then, because $\lVert M\rVert_{0}\leq t$, $M$ has fewer than $\sqrt{t}$ non-
zero rows. It follows that all non-zero columns of $M$ are $\sqrt{t}$-sparse.
∎

We now prove our main theorem about deterministic MMV.

######  Theorem 3.2 (Fast deterministic MMV for sparse matrices, formal).

Let $0\leq\delta\leq 2$ be a constant, and $\mathbb{F}_{q}$ be a finite field.
Then for every constant $\varepsilon>0$, there is a deterministic algorithm
for $\textrm{MMV}_{\mathbb{F}_{q}}^{n^{\delta}}$ that runs in
$n^{\omega(1,1,\delta/2)+\varepsilon}\cdot\operatorname{poly}(\log{q})$ time.

###### Proof.

From Theorem 2.8, it is sufficient to construct a deterministic algorithm
solving the $\textrm{AllZeroes}_{\mathbb{F}}^{n^{\delta}}$ problem with the
same guarantee on the running time. If $q<n$, then we consider
$\mathbb{F}=\mathbb{F}_{r}$, a field extension of $\mathbb{F}_{q}$, where
$n\leq r<n^{2}$. (Such a field can be constructed in deterministic time
$\widetilde{O}(n)$ [Sho90]). If $q\geq n$, then we simply set
$\mathbb{F}=\mathbb{F}_{q}$. We remark that $AB=0$ over $\mathbb{F}_{q}$ if
and only if $AB=0$ over $\mathbb{F}$, and that all arithmetic operations over
$\mathbb{F}$ can be performed in time $\operatorname{poly}(\log{q},\log{n})$
(see, e.g., [Sho09]). In the following, given two matrices
$A,B\in\mathbb{F}^{n\times n}$, with the guarantee that $\lVert
AB\rVert_{0}\leq n^{\delta}$, we will determine if $AB=0$.

Let $H\in\mathbb{F}^{n^{\delta/2}\times n}$ be the parity check matrix from
Corollary 2.12 with $k=n-n^{\frac{\delta}{2}}$ computed in time
$n^{2}\cdot\operatorname{poly}(\log{q})$. Our algorithm reports that $AB=0$ if
and only if both $HAB=0$ and $H(AB)^{T}=0$.

Since the matrix $H$ is computed in time
$n^{2}\cdot\operatorname{poly}(\log{q},\log{n})$, and computing the matrix
products $HAB$ and $H(AB)^{T}$ takes time
$n^{\omega(1,1,\delta/2)+\varepsilon}\cdot\operatorname{poly}(\log{q})$ for
any constant $\varepsilon>0$, we conclude the desired bound on the running
time of the algorithm.

It remains to prove the correctness of the algorithm. First, if $AB=0$, then
$HAB=H(AB)^{T}=0$ for all matrices $H$, and, therefore, our algorithm
correctly concludes that $AB=0$. Now, suppose that $AB\neq 0$. If a non-zero
column $\boldsymbol{c}$ of $AB$ has $\lVert\boldsymbol{c}\rVert_{0}\leq
n^{\delta/2}$ then $H\boldsymbol{c}\neq\boldsymbol{0}$ by Corollary 2.12 and
so $HAB\neq 0$. Similarly, if a non-zero row $\boldsymbol{r}$ of $AB$ has
$\lVert\boldsymbol{r}\rVert_{0}\leq n^{\delta/2}$ then
$H\boldsymbol{r}^{T}\neq\boldsymbol{0}$ and so $H(AB)^{T}\neq 0$. Moreover,
Lemma 3.1 implies that $AB$ has a non-zero, $n^{\delta/2}$-sparse row or
column, and so the theorem follows.

∎

We now show how to extend Theorem 3.2 to the case of MMV over the integers.

(1) Let $k:=\lceil{\sqrt{t}}\rceil$. (2) Compute an arbitrary prime $p$ that
satisfies $n\leq p\leq 2n$. (3) Compute a (parity check) matrix
$H\in\mathbb{F}_{p}^{k\times n}$ as in Corollary 2.12. (4) Output YES if
$H(AB-C)=0$ and $H(AB-C)^{T}=0$ (where arithmetic is performed over
$\mathbb{Z}$), and output NO otherwise. Figure 1: Deterministic Algorithm for
$\textrm{MMV}_{\mathbb{Z}}^{t}$.

######  Corollary 3.3.

Let $0\leq\delta\leq 2$ be a constant. Then for every $\varepsilon>0$, there
is a deterministic algorithm (given in Figure 1) for
$\textrm{MMV}_{\mathbb{Z}}^{n^{\delta}}$ for matrices with entries from
$[-M,M]$ that runs in
$n^{\omega(1,1,\delta/2)+\varepsilon}\cdot\operatorname{poly}(\log{M})$ time.

###### Proof.

The algorithm follows the high level idea of the algorithm from Theorem 3.2
with a few modifications that we describe below. We present an algorithm for
the $\textrm{AllZeroes}_{\mathbb{Z}}^{n^{\delta}}$ problem, and use Theorem
2.8 to conclude an algorithm for the $\textrm{MMV}_{\mathbb{Z}}^{n^{\delta}}$
problem. Let $p$ be an arbitrary prime satisfying $n\leq p<2n$. Such prime can
be found in deterministic time $\widetilde{O}(n)$ using the Sieve of
Eratosthenes (see, e.g., [vzGG13, Theorem 18.10 (ii)]). Let
$H\in\mathbb{F}_{p}^{n^{\delta/2}\times n}$ be the parity check matrix from
Corollary 2.12 with $k=n-n^{\delta/2}$ computed in time
$n^{2}\cdot\operatorname{poly}(\log{n})$. Our algorithm reports that $AB=0$ if
and only if $HAB=H(AB)^{T}=0$, where the multiplication is over the integers.

The running time of the algorithm is dominated by the time required to compute
rectangular matrix multiplication,
$n^{\omega(1,1,\delta/2)+\varepsilon}\cdot\operatorname{poly}(\log{M})$ for
any $\varepsilon>0$. If $AB=0$, then $HAB=H(AB)^{T}=0$ for every $H$. Now, if
$AB\neq 0$, we can conclude that $AB$ contains a non-zero column or row vector
of sparsity at most $n^{\delta/2}$. Let $\boldsymbol{c}\in\mathbb{Z}^{n}$ be a
nonzero column of $AB$ of sparsity $\lVert\boldsymbol{c}\rVert_{0}\leq
n^{\delta/2}$. Assume that $H\boldsymbol{c}=\boldsymbol{0}$ where the
multiplication is over the integers. We factor out the largest power of $p$
dividing all coefficients of $\boldsymbol{c}$, and obtain a non-zero vector
$\boldsymbol{c}^{\prime}\in\mathbb{F}_{p}^{n}$,
$\lVert\boldsymbol{c}^{\prime}\rVert_{0}\leq n^{\delta/2}$ such that
$H\boldsymbol{c}^{\prime}=\boldsymbol{0}$ where the multiplication is over
$\mathbb{F}_{p}$. This contradicts the guarantee of Corollary 2.12. Therefore,
$H\boldsymbol{c}\neq\boldsymbol{0}$, and our algorithm detects that $AB\neq C$
in this case. Similarly, in the case when $AB$ contains a non-zero row of
sparsity at most $n^{\delta/2}$, the algorithm detects that $AB\neq 0$ from
$H(AB)^{T}\neq 0$. ∎

We again remark that the algorithm from Corollary 3.3 outperforms the
currently best known algorithm from [Kün18] for
$\text{MMV}_{\mathbb{Z}}^{n^{\delta}}$ for every $\delta\geq 1.055322$.
Indeed, the algorithm from [Kün18] runs in time
$\widetilde{O}({n^{1+\delta}})$, while the running time of the algorithm from
Corollary 3.3 is
$\widetilde{O}\left(n^{\omega(1,1,\delta/2)+\varepsilon}\right)$ for any
$\varepsilon>0$. From Table 1 in [VXXZ23], the latter running time is
asymptotically better than the former one for every $\delta/2>0.527661$.

If the matrix multiplication exponent $\omega=2$, then the MMV problem can be
solved in time $n^{2+\varepsilon}$ for every $\varepsilon>0$. Below we show
that even if $\omega>2$, then our algorithm solves
$\textrm{MMV}_{\mathbb{Z}}^{n^{\delta}}$ in better-than-$n^{\omega}$ time for
every constant $\delta<2$.

######  Corollary 3.4.

If $\omega>2$, then for every $0\leq\delta<2$ there exists an $\alpha>0$, and
a deterministic algorithm for $\textrm{MMV}_{\mathbb{Z}}^{n^{\delta}}$ for
matrices with entries from $[-M,M]$ that runs in
$n^{\omega-\alpha}\cdot\operatorname{poly}(\log{M})$ time.

###### Proof.

The running time of the algorithm from Corollary 3.3 is
$n^{\omega(1,1,\delta/2)+\varepsilon}$ for any $\varepsilon>0$.

If $\delta\leq 2\omega^{\perp}$, then by Theorem 2.3,
$\omega(1,1,\delta/2)=2<\omega$. Setting $\varepsilon=\alpha=(\omega-2)/2>0$,
we have that the running time of the algorithm is bounded from above by

$n^{2+\varepsilon}\cdot\operatorname{poly}(\log{M})=n^{\omega-\alpha}\cdot\operatorname{poly}(\log{M})\,.$

If $\delta>2\omega^{\perp}$, then by Theorem 2.3,

$\omega(1,1,\delta/2)\leq
2+(\omega-2)\dfrac{\delta/2-\omega^{\perp}}{1-\omega^{\perp}}\,.$

In this case, setting

$\alpha=\varepsilon=\dfrac{(\omega-2)(1-\delta/2)}{2(1-\omega^{\perp})}>0\,,$

we have that the algorithm runs in time

$n^{\omega(1,1,\delta/2)+\varepsilon}\cdot\operatorname{poly}(\log{M})=n^{\omega-\alpha}\cdot\operatorname{poly}(\log{M})\,.\qed$

Interestingly, Corollary 3.4 reduces the problem of constructing faster-
than-$n^{\omega}$ algorithms for AllZeroes to the following gap problem:
Distinguish the case where the product of two matrices has
$\Omega(n^{2-\varepsilon})$ non-zero entries and the case where the product is
identically zero. As noted in Section 1.2, this leads to a surprising
situation: on the one hand, for every $\varepsilon>0$, if the product of the
two matrices is $n^{2-\varepsilon}$-sparse, then there is an
$n^{\omega-\alpha}$-time deterministic algorithm for $\alpha>0$; on the other
hand, if the product is $\Omega(n^{2-\varepsilon})$-dense, then there is
randomized algorithm that runs in time $\widetilde{O}(n^{1+\varepsilon})$ and
reads only $\widetilde{O}(n^{1+\varepsilon})$ entries of the input matrices.

###  3.2 Randomized MMV for Sparse Matrices

In this section, we extend our framework to the setting of randomness-
efficient probabilistic algorithms for MMV. We combine our results conditioned
on sparsity along with [KS93] to get the best known randomized algorithm for
MMV in both running time, and random bits used. In Theorem 3.5, we present an
algorithm for MMV over finite fields, and in Corollary 3.6 we extend it to the
case of matrices over the integers.

######  Theorem 3.5 (Fast randomized MMV for sparse matrices, formal).

Let $0\leq\delta\leq 2$ be a constant, and $\mathbb{F}_{q}$ be a finite field.
Then for every $\varepsilon>0$, there is a randomized algorithm for
$\textrm{MMV}_{\mathbb{F}_{q}}^{n^{\delta}}$ that runs in
$n^{2}\cdot\operatorname{poly}(\log(nq/\varepsilon))$ time, succeeds with
probability $1-\varepsilon$, and uses at most
$\lceil{\delta/2\cdot\log_{2}(n)+\log_{2}(1/\varepsilon)}\rceil$ bits of
randomness.

###### Proof.

Let $k=\lceil{n^{\delta/2}/\varepsilon}\rceil$. If $q<k+n$, then we consider
$\mathbb{F}=\mathbb{F}_{r}$, a field extension of $\mathbb{F}_{q}$, where
$k+n\leq r<(k+n)^{2}$, otherwise we set $\mathbb{F}=\mathbb{F}_{q}$. We note
that $\mathbb{F}$ can be constructed in time
$q\cdot\operatorname{poly}(\log(kq))=n^{2}\cdot\operatorname{poly}(\log(nq/\varepsilon))$
[Sho90], all arithmetic operations over $\mathbb{F}$ can be performed in time
$\operatorname{poly}(\log|\mathbb{F}|)=\operatorname{poly}(\log(nq/\varepsilon))$
[Sho09], and that $AB=C$ over $\mathbb{F}$ if and only if $AB=C$ over
$\mathbb{F}_{q}$.

Let $S\in\mathbb{F}^{n\times k}$ be an $n^{\delta/2}$-regular matrix, and
$\boldsymbol{s}\in\mathbb{F}^{n}$ be a uniformly random column of $S$. Our
algorithm reports that $AB=C$ if and only if
$AB\boldsymbol{s}=C\boldsymbol{s}$ and
$(AB)^{T}\boldsymbol{s}=C^{T}\boldsymbol{s}$. In the following, we will show
that the running time of the algorithm is
$n^{2}\cdot\operatorname{poly}(\log(nq/\varepsilon))$, the number of random
bits used is $\lceil{\delta/2\cdot\log_{2}(n)+\log_{2}(1/\varepsilon)}\rceil$,
and finally we will prove the correctness of the algorithm.

From Corollary 2.17, one can compute $\boldsymbol{s}$ in deterministic time
$n\cdot\operatorname{poly}(\log(nq/\varepsilon))$. Each of $AB\boldsymbol{s}$
and $(AB)^{T}\boldsymbol{s}$ can be computed by two vector-matrix
multiplications in deterministic
${n^{2}\cdot\operatorname{poly}(\log(nq/\varepsilon))}$ time.

The described algorithm only uses randomness to generate a uniformly random
column index $1\leq i\leq k$, which requires
$\lceil{\log_{2}(k)}\rceil=\lceil{\delta/2\cdot\log_{2}(n)+\log_{2}(1/\varepsilon)}\rceil$
random bits.

If $AB=C$, then for every vector $\boldsymbol{s}$, we have
$AB\boldsymbol{s}=C\boldsymbol{s}$ and
$(AB)^{T}\boldsymbol{s}=C^{T}\boldsymbol{s}$, and the algorithm correctly
concludes that $AB=C$. For the case when $AB\neq C$, we want the algorithm to
detect this with probability at least $1-\varepsilon$. To this end, we will
show that for every $n^{\delta/2}$-regular matrix $S\in\mathbb{F}^{n\times
k}$, either the matrix $ABS$ or the matrix $(AB)^{T}S$ has at least
$1-\varepsilon$ fraction of non-zero columns.

By Lemma 3.1, if $\lVert AB-C\rVert_{0}\leq n^{\delta}$, then $AB-C$ contains
a non-zero row or column of sparsity at most $n^{\delta/2}$. Let us first
consider the case where $AB-C$ has a non-zero row
$\boldsymbol{r}\in\mathbb{F}^{n}$ of sparsity at most $n^{\delta/2}$. We will
show that $\boldsymbol{r}S$ has fewer than $n^{\delta/2}$ zero coordinates.
This will finish the proof, as the success probability of our algorithm is at
least the probability of sampling a column where $\boldsymbol{r}S$ is non-
zero, which is at least $1-n^{\delta/2}/k\geq 1-\varepsilon$.

Assume, towards a contradiction, that $\boldsymbol{r}S$ has at least
$n^{\delta/2}$ zero coordinates. Let $I\subseteq[n],|I|=n^{\delta/2}$ be an
arbitrary set containing (the indices of) all non-zero coordinates of
$\boldsymbol{r}$, and let $J\subseteq[n],|J|=n^{\delta/2}$ be a set of indices
of some $n^{\delta/2}$ zero coordinates of $\boldsymbol{r}S$. Then the matrix
$S$ restricted to the rows $I$ and columns $J$ is singular (the linear
combination of these rows, given by the non-zero vector $\boldsymbol{r}$, is
$\boldsymbol{0}$). On the other hand, since $S$ is $n^{\delta/2}$-regular, $S$
restricted to $I$ and $J$ is non-singular, which leads to a contradiction.
Similarly, in the case when $AB-C$ has a non-zero column
$\boldsymbol{c}\in\mathbb{F}^{n}$ of sparsity at most $n^{\delta/2}$, our
algorithm will detect that $AB\neq C$ with probability at least
$1-\varepsilon$ by checking $(AB)^{T}\boldsymbol{s}=C^{T}\boldsymbol{s}$. ∎

Below we show how to extend the algorithm of Theorem 3.5 to the case of
integer matrices.

(1) Let $k:=\lceil{\sqrt{t}/\varepsilon}\rceil$. (2) Compute an arbitrary
prime $p$ satisfying $k+n\leq p<2(k+n)$. (3) Compute a
$\lceil{\sqrt{t}}\rceil$-regular matrix
$S=(\boldsymbol{s}_{1},\ldots,\boldsymbol{s}_{k})\in\mathbb{Z}^{n\times k}$ as
in Corollary 2.17. (4) Sample a uniformly random column index
$i\sim\\{{1,\ldots,k}\\}$. (5) Output YES if
$AB\boldsymbol{s}_{i}=C\boldsymbol{s}_{i}$ and
$(AB)^{T}\boldsymbol{s}_{i}=C^{T}\boldsymbol{s}_{i}$ (where arithmetic is
performed over $\mathbb{Z}$), and output NO otherwise. Figure 2: Randomized
Algorithm for $\textrm{MMV}_{\mathbb{Z}}^{t}$.

######  Corollary 3.6.

Let $0\leq\delta\leq 2$ be a constant. Then for every $\varepsilon>0$, there
is a randomized algorithm (given in Figure 2) for
$\textrm{MMV}_{\mathbb{Z}}^{n^{\delta}}$ for matrices with entries from
$[-M,M]$ that runs in
$n(n+1/\varepsilon)\cdot\operatorname{poly}(\log(nM/\varepsilon))$ time,
succeeds with probability $1-\varepsilon$, and uses at most
$\lceil{\delta/2\cdot\log_{2}(n)+\log_{2}(1/\varepsilon)}\rceil$ bits of
randomness. In particular, when $\varepsilon\geq 1/n$, the algorithm runs in
$n^{2}\cdot\operatorname{poly}(\log n,\log M)$ time.

###### Proof.

Let $k=\lceil{n^{\delta/2}/\varepsilon}\rceil$, and $p$ be an arbitrary prime
$p$ satisfying $k+n\leq p<2(k+n)$. Let $S\in\mathbb{F}_{p}^{n\times k}$ be an
$n^{\delta/2}$-regular matrix, and $\boldsymbol{s}\in\mathbb{F}_{p}^{n}$ be a
uniformly random column of $S$. Our algorithm reports that $AB=C$ if and only
if $AB\boldsymbol{s}=C\boldsymbol{s}$ and
$(AB)^{T}\boldsymbol{s}=C^{T}\boldsymbol{s}$, where the multiplication is over
$\mathbb{Z}$.

Using the Sieve of Eratosthenes (see, e.g., [vzGG13, Theorem 18.10 (ii)]), one
can find a prime $p$ satisfying $k+n\leq p<2(k+n)$ in deterministic time
$\widetilde{O}(k+n)\leq(n/\varepsilon)\cdot\operatorname{poly}(\log(n/\varepsilon))$.
From Corollary 2.17, $s$ can be computed in deterministic time
$n\cdot\operatorname{poly}(\log(n/\varepsilon))$. Finally $AB\boldsymbol{s}$
and $(AB)^{T}\boldsymbol{s}$ can be computed in time
$n^{2}\cdot\operatorname{poly}(\log(nM/\varepsilon))$. The algorithm uses
$\lceil{\log_{2}(k)}\rceil=\lceil{\delta/2\cdot\log_{2}(n)+\log_{2}(1/\varepsilon)}\rceil$
random bits to generate a uniformly random column index $1\leq i\leq k$.

If $AB=C$, then for every vector $\boldsymbol{s}$, we have
$AB\boldsymbol{s}=C\boldsymbol{s}$ and
$(AB)^{T}\boldsymbol{s}=C^{T}\boldsymbol{s}$, and the algorithm correctly
concludes that $AB=C$. Assume that $AB\neq C$. Since $\lVert
AB-C\rVert_{0}\leq n^{\delta}$, $AB-C$ contains a non-zero row or column of
sparsity at most $n^{\delta/2}$. We will assume that $AB-C$ has a non-zero row
$\boldsymbol{r}\in\mathbb{Z}^{n}$ of sparsity at most $n^{\delta/2}$ (the
other case is analogous to this one). Assume, towards a contradiction, that
$\boldsymbol{r}S$ has at least $n^{\delta/2}$ zero coordinates. Let
$I\subseteq[n],|I|=n^{\delta/2}$ be an arbitrary set containing (the indices
of) all non-zero coordinates of $\boldsymbol{r}$, and let
$J\subseteq[n],|J|=n^{\delta/2}$ be a set of indices of some $n^{\delta/2}$
zero coordinates of $\boldsymbol{r}S$. Then the matrix $S$ restricted to the
rows $I$ and columns $J$ is singular over the integers. On the other hand,
since $S$ is $n^{\delta/2}$-regular, $S$ restricted to $I$ and $J$ is non-
singular over $\mathbb{F}_{p}$, and, thus, over $\mathbb{Z}$. This leads to a
contradiction. Therefore, $\boldsymbol{r}S$ has at most $n^{\delta/2}$ zero
coordinates, and $ABS$ contains at least $k-n^{\delta/2}\geq(1-\varepsilon)k$
non-zero columns. ∎

###  3.3 A Barrier for Linear Algebraic Approaches to MMV

In this section, we give a barrier for algorithms for the AllZeroes problem
that are based on “zero tests.” On an input instance $A,B$, such zero tests
compute the matrix product $L(AB)R$ for fixed
$L\in\mathbb{F}^{n^{\alpha}\times n}$ and $R\in\mathbb{F}^{n\times n^{\beta}}$
with $\alpha,\beta\in[0,1]$ and report “$AB=0$” if and only if $L(AB)R=0$. In
fact, we consider algorithms based on $k$ such tests, i.e., algorithms that
report “$AB=0$” if and only if $L_{i}(AB)R_{i}=0$ for fixed
$L_{i}\in\mathbb{F}^{n^{\alpha_{i}}\times n}$ and $R_{i}\in\mathbb{F}^{n\times
n^{\beta_{i}}}$ with $\alpha_{i},\beta_{i}\in[0,1]$ for $i=1,\ldots,k$. This
approach captures a large class of algorithms for MMV, including our
deterministic algorithm presented in Figure 1.

In Theorem 3.7, we show a barrier to getting a fast algorithm using this
approach to MMV. The idea behind the barrier is as follows. Treating the
$n^{2}$ entries $C_{i,j}$ of $C=AB$ as variables, the $i$th zero test
$L_{i}ABR_{i}$ for fixed $L_{i}\in\mathbb{F}^{n^{\alpha_{i}}\times n},R_{i}\in
F^{n\times n^{\beta_{i}}}$ corresponds to a system of
$n^{\alpha_{i}+\beta_{i}}$ homogeneous linear equations. So, for $AB=C=0$ to
be the unique solution to this system of equations, we must have
$\sum_{i=1}^{k}n^{\alpha_{i}+\beta_{i}}\geq n^{2}$.

######  Theorem 3.7.

Let $\mathbb{F}$ be a field, $k$ be an integer, and for every $1\leq i\leq k$,
$L_{i}\in\mathbb{F}^{n^{\alpha_{i}}\times n},R_{i}\in\mathbb{F}^{n\times
n^{\beta_{i}}}$ be matrices such that
$\operatorname{rank}(L_{i})=n^{\alpha_{i}}$ and
$\operatorname{rank}(R_{i})=n^{\beta_{i}}$ for $0\leq\alpha_{i},\beta_{i}\leq
1$. Assume that for all $A,B\in\mathbb{F}^{n\times n}$, $AB=0$ if and only if
$L_{i}ABR_{i}=0$ for all $1\leq i\leq k$. Then

$\displaystyle\sum_{i=1}^{k}n^{\alpha_{i}+\beta_{i}}\geq n^{2}\,,\text{ and}$
$\displaystyle\sum_{i=1}^{k}n^{\omega(1,1,\min(\alpha_{i},\beta_{i}))}\geq\sum_{i=1}^{k}n^{\omega(\alpha_{i},1,\beta_{i})}\geq
n^{\omega}\,.$

###### Proof.

Let $C=AB$, and let us view each of the $n^{2}$ entries $C_{i,j}$ of $C$ as a
variable. Then each constraint $L_{i}CR_{i}=0$ induces a homogeneous system of
$n^{\alpha_{i}+\beta_{i}}$ linear equations over these variables, and the
constraints together induce a system of
$\sum_{i=1}^{k}n^{\alpha_{i}+\beta_{i}}$ such equations. In order for a
homogeneous system of linear equations to have $C=0$ (the all-zeroes solution)
as its only solution, the number of equations needs to be at least $n^{2}$.
Hence, we have that $\sum_{i=1}^{k}n^{\alpha_{i}+\beta_{i}}\geq n^{2}$.
Furthermore, by Lemma 2.4,
$\omega(\alpha_{i},1,\beta_{i})\geq\omega-2+\alpha_{i}+\beta_{i}$. This
implies that

$\sum_{i=1}^{k}n^{\omega(1,1,\min(\alpha_{i},\beta_{i}))}\geq\sum_{i=1}^{k}n^{\omega(\alpha_{i},1,\beta_{i})}\geq\sum_{i=1}^{k}n^{\omega-2+\alpha_{i}+\beta_{i}}\geq
n^{\omega-2}\cdot\sum_{i=1}^{k}n^{\alpha_{i}+\beta_{i}}\geq n^{\omega}\,,$

which finishes the proof. ∎

From Theorem 3.7, we get the following corollary, which says that any
algorithm for MMV using “zero tests” and computing the matrix each of the
matrix products $L_{i}ABR_{i}$ independently in
$\Omega(n^{\omega(1,1,\min(\alpha_{i},\beta_{i}))})$ time runs in
$\Omega(n^{\omega})$ time. We note that
$\Omega(n^{\omega(1,1,\min(\alpha_{i},\beta_{i}))})$ lower bounds the minimum
worst-case cost of multiplying (1) a $n^{\alpha_{i}}\times n$ and an $n\times
n$ matrix and (2) an $n\times n$ matrix and an $n\times n^{\beta_{i}}$ matrix.
Any parenthesization of $L_{i}ABR_{i}$ (e.g., $L_{i}(A(BR_{i}))$) requires
computing a matrix product either of form (1) or (2).

######  Corollary 3.8.

Let $\mathcal{A}$ be an algorithm for $\text{MMV}_{\mathbb{F}}$ that behaves
in the following way. On input $A,B\in\mathbb{F}^{n\times n}$, $\mathcal{A}$
computes matrices $L_{1},R_{1},\ldots,L_{k},R_{k}$ with
$L_{i}\in\mathbb{F}^{n^{\alpha_{i}}\times
n},R_{i}\in\mathbb{F}^{n^{\beta_{i}}}$ for $0\leq\alpha_{i},\beta_{i}\leq 1$
such that $AB=0$ if and only if $L_{i}ABR_{i}=0$ for all $1\leq i\leq k$. It
then computes each product $L_{i}ABR_{i}$ independently using
$\Omega(n^{\omega(1,1,\min(\alpha_{i},\beta_{i}))})\geq\Omega(n^{\omega(\alpha_{i},1,\beta_{i})})$
time. Then $\mathcal{A}$ runs in $\Omega(n^{\omega})$ time.

We note that Corollary 3.8 does _not_ rule out more clever ways of computing
the matrix products $L_{i}ABR_{i}$, such as exploiting the structure of
$L_{i},R_{i}$ or computing multiple products simultaneously. However, a
stronger version of Corollary 3.8 with a more subtle proof does seem to rule
out some of these algorithm variants too.

##  4 On the non-SETH-hardness of Matrix Multiplication

In this section, we show a barrier for proving a lower bound for Matrix
Multiplication (and, thus, for MMV) under SETH. More specifically, we show
that such a result would imply either super-linear circuit lower bounds, or an
explicit construction of rigid matrices.

###  4.1 A Nondeterministic Algorithm for Multiplying Non-Rigid Matrices

We will use the following algorithm for multiplying sparse matrices.

######  Theorem 4.1 ([YZ05, Theorem 3.1]).

Let $\mathbb{F}$ be a field, $0\leq s\leq 2$, and $A,B\in\mathbb{F}^{n\times
n}$ be $n^{s}$-sparse matrices. If $\omega>2$, then there is a deterministic
algorithm that computes $AB$ using

$n^{(2s(\omega-2)+2-\omega\omega^{\perp})/(\omega-1-\omega^{\perp})+o(1)}$

arithmetic operations over $\mathbb{F}$.

For every $\gamma\geq 2$, we define the largest matrix sparsity and the
largest dimension of rectangular matrices, such that matrix product can be
computed in time $n^{\gamma}$.

######  Definition 4.2.

For every $\gamma\geq 2$, let

$\displaystyle r(\gamma)$
$\displaystyle:=\sup\\{{r>0:\omega(1,1,r)\leq\gamma}\\}\,,$ $\displaystyle
s(\gamma)$ $\displaystyle:=\sup\\{{s>0:\text{product of $n^{s}$-sparse
matrices can be computed in $n^{\gamma}$ field operations}}\\}\,.$

Assuming $\omega>2$, for all $\gamma>2$, from Theorem 2.3 and Theorem 4.1 we
have that

$\displaystyle r(\gamma)$
$\displaystyle\geq\frac{(\gamma-2)(1-\omega^{\perp})}{\omega-2}+\omega^{\perp}\,,$
(5) $\displaystyle s(\gamma)$
$\displaystyle\geq\frac{\gamma(\omega-1-\omega^{\perp})+\omega\omega^{\perp}-2}{2(\omega-2)}\,.$
(6)

We now present a simple _non-deterministic_ algorithm that efficiently
multiplies non-rigid matrices.

######  Lemma 4.3.

Let $\mathbb{F}_{q}$ be a finite field, $\gamma\geq 2$ be a constant, and let
$A,B\in\mathbb{F}_{q}^{n\times n}$ be two matrices satisfying

$\displaystyle{\mathcal{R}}_{n^{r(\gamma)}}^{\mathbb{F}_{q}}(A)\leq
n^{s(\gamma)}\,,\quad{\mathcal{R}}_{n^{r(\gamma)}}^{\mathbb{F}_{q}}(B)\leq
n^{s(\gamma)}\,.$

Then for every $\alpha>0$, there is a non-deterministic algorithm that
computes $AB$ in time $n^{\gamma+\alpha}\cdot\operatorname{poly}(\log{q})$.

###### Proof.

First, we non-deterministically guess decompositions of the non-rigid matrices
$A$ and $B$ into the sum of a low-rank matrix and a sparse matrix, and then
guess a rank factorization of the two low-rank matrices. More specifically, we
non-deterministically guess a tuple $(L_{A},R_{A},S_{A},L_{B},R_{B},S_{B})$
such that

  * •

$A=L_{A}\cdot R_{A}+S_{A}$ and $B=L_{B}\cdot R_{B}+S_{B}$;

  * •

$L_{A},L_{B}\in\mathbb{F}_{q}^{n\times n^{r(\gamma)}}$, and
$R_{A},R_{B}\in\mathbb{F}_{q}^{n^{r(\gamma)}\times n}$;

  * •

$S_{A},S_{B}\in\mathbb{F}_{q}^{n\times n}$, $S_{A}$ and $S_{B}$ are
$n^{s(\gamma)}$-sparse.

By the definition of rigidity (Definition 2.23), such decompositions exist for
all matrices $A,B$ satisfying the premise of the lemma. To verify the
decomposition, we need to

  * •

compute $L_{A}\cdot R_{A}$ and $L_{B}\cdot R_{B}$ in deterministic
$n^{\gamma+\alpha}\cdot\operatorname{poly}(\log{q})$ time;

  * •

verify that $S_{A}$ and $S_{B}$ are $n^{s(\gamma)}$-sparse in deterministic
$n^{2}\cdot\operatorname{poly}(\log{q})$ time;

  * •

check that $A=L_{A}\cdot R_{A}+S_{A}$ and $B=L_{B}\cdot R_{B}+S_{B}$ in
deterministic $n^{2}\cdot\operatorname{poly}(\log{q})$ time.

Now we will present a deterministic algorithm that runs in time
$n^{\gamma+\alpha}\cdot\operatorname{poly}(\log{q})$ and computes the product

$AB=(L_{A}\cdot R_{A}+S_{A})(L_{B}\cdot R_{B}+S_{B})=L_{A}\cdot R_{A}\cdot
L_{B}\cdot R_{B}+L_{A}\cdot R_{A}\cdot S_{B}+S_{A}\cdot L_{B}\cdot
R_{B}+S_{A}\cdot S_{B}\,.$

Recall from Theorem 2.5 that
$\omega(r(\gamma),1,1)=\omega(1,r(\gamma),1)=\omega(1,1,r(\gamma))$. Then the
first three terms in the sum above can be computed using rectangular matrix
multiplication in time

$n^{\omega(1,1,r(\gamma))+\alpha}\cdot\operatorname{poly}(\log{q})\leq
n^{\gamma+\alpha}\cdot\operatorname{poly}(\log{q})\,.$

Finally, since $S_{A}$ and $S_{B}$ are $n^{s(\gamma)}$-sparse, the term
$S_{A}\cdot S_{B}$ can be computed in time
$n^{\gamma+\alpha}\cdot\operatorname{poly}(\log{q})$. This finishes the proof
of the lemma. ∎

###  4.2 The Main SETH-Hardness Barrier Result

We are now ready to present the main result of this section: a barrier to
proving SETH-hardness of Matrix Multiplication (and hence also of Matrix
Multiplication Verification). Below, by
$\mathsf{QP}=\mathsf{DTIME}[n^{\operatorname{poly}(\log n)}]$ we denote the
class of deterministic algorithms running in quasi-polynomial time.

######  Theorem 4.4.

Let $q$ be a prime power. If Matrix Multiplication over $\mathbb{F}_{q}$ is
$n^{\gamma}\cdot\operatorname{poly}(\log{q})$-SETH-hard for a constant
$\gamma>2$, then one of the following holds:

  * •

NSETH is false.

  * •

There is a $\mathsf{QP}^{\mathsf{NP}}$ algorithm ${\cal A}$ such that for
infinitely many values of $N$, ${\cal A}(1^{N})$ outputs a matrix
$A\in\mathbb{F}_{q}^{M\times M}$ satisfying

${\mathcal{R}}_{M^{r(\gamma^{\prime})}}^{\mathbb{F}_{q}}(A)\geq
M^{s(\gamma^{\prime})}$

for any $\gamma^{\prime}<\gamma$, where $M=N^{\Theta(1)}$. Specifically, the
running time of the algorithm $\cal{A}$ on input $1^{N}$ is
$N^{O(\log\log{N})}$.

###### Proof.

The high-level idea of the proof is the following. Assume there is a fine-
grained reduction $R_{k}$ from $k$-SAT to $\textrm{MM}_{\mathbb{F}_{q}}$ for
every $k$. For every $k$-SAT formula on $n$ variables, $R_{k}$ adaptively
produces a (possibly exponentially large) sequence of MM instances. If for all
large enough $n$, all the produced matrices are non-rigid, then from Lemma 4.3
we have an efficient non-deterministic algorithm for all encountered instances
of MM, and, thus, an efficient non-deterministic algorithm for $k$-TAUT. This
refutes NSETH. On the other hand, if for infinitely many values of $n$, at
least some of the produced instances of MM are rigid, then we have an
algorithm that brute forces all $k$-SAT instances, applies $R$ to them, and
then uses the $\mathsf{NP}$ oracle to verify if they are rigid. We will show
that this algorithm finds rigid matrices $M\in\mathbb{F}_{q}^{N\times N}$ in
time $N^{O(\log\log N)}$ with an $\mathsf{NP}$ oracle. Below we formalize this
argument.

Assume that $\textrm{MM}_{\mathbb{F}_{q}}$ is $n^{\gamma}$-SETH-hard (see
Definition 2.22). Then there exists a function
$\delta\colon\mathbb{R}_{>0}\to\mathbb{R}_{>0}$ such that for every
$k\in\mathbb{N}$,
$(k\text{-SAT},2^{n})\leq_{\delta}(\textrm{MM}_{\mathbb{F}_{q}},n^{\gamma})$.
Let us fix $\varepsilon_{0}=(\gamma-\gamma^{\prime})/(2\gamma)\in(0,1)$ and
$\delta_{0}=\delta(\varepsilon_{0})\in(0,1)$, where $\delta$ is the function
from the definition of SETH-hardness. For every $k$, let $R_{k}$ be the fine-
grained reduction from $k$-SAT to $\textrm{MM}_{\mathbb{F}_{q}}$ guaranteed by
the $n^{\gamma}$-SETH-hardness of $\textrm{MM}_{\mathbb{F}_{q}}$. An
$n^{\gamma(1-\varepsilon_{0})}$-time algorithm for
$\textrm{MM}_{\mathbb{F}_{q}}$ would imply (via $R_{k}$) a
$2^{n(1-\delta_{0})}$-time algorithm for $k$-SAT. In particular, the reduction
$R_{k}$ runs in time $O(2^{n(1-\delta_{0})})$.

For every $k$, let us consider the following algorithm ${\cal A}_{k}$ equipped
with an $\mathsf{NP}$ oracle. On input $1^{N}$, if $N$ is not a power of two,
the algorithm halts. Otherwise, the algorithm sets $n=\log_{2}{N}$ and
$\lambda=\delta_{0}/4$. Let $c=c(k,\lambda)$ be the constant from the
Sparsification Lemma (Theorem 2.20). The algorithm ${\cal A}_{k}$ enumerates
all $k$-SAT formulas with $n$ variables and at most $cn$ clauses, applies the
fine-grained reduction $R_{k}$ to each of them, solves all queried instances
of $\textrm{MM}_{\mathbb{F}_{q}}$ by the trivial cubic-time algorithm, and
this way adaptively obtains all MM instances produced by $R_{k}$. Let us
denote these instances of MM by $(A_{1},B_{1}),\ldots,(A_{T},B_{T})$. For each
instance $(A_{i},B_{i})$ where $A_{i},B_{i}\in\mathbb{F}_{q}^{M\times M}$, if
$M>2^{\delta_{0}n/12}$ the algorithm checks if it satisfies

${\mathcal{R}}_{M^{r(\gamma^{\prime})}}^{\mathbb{F}_{q}}(A_{i}),{\mathcal{R}}_{M^{r(\gamma^{\prime})}}^{\mathbb{F}_{q}}(B_{i})\geq
M^{s(\gamma^{\prime})}\,.$

Since the problem of checking rigidity is trivially in $\mathsf{coNP}$, ${\cal
A}_{k}$ checks this using the $\mathsf{NP}$ oracle. If ${\cal A}_{k}$ finds a
rigid matrix, it outputs the first such found matrix, otherwise it outputs
nothing.

Now we bound the running time of the algorithms ${\cal A}_{k}$. Enumeration of
all $k$-SAT instances with $n$ variables and $cn$ clauses takes time
$\binom{O(n^{k})}{\leq cn}=2^{O(n\log{n})}$. The running time of the
Sparsification Lemma is $2^{\lambda n}=2^{\delta_{0}n/4}$. The running time of
each execution of the fine-grained reduction is $O(2^{n(1-\delta_{0})})$, and
the time needed to perform each matrix multiplication is at most
$O(2^{3n(1-\delta_{0})})$. This leads to the total running time of
$2^{O(n\log{n})}=N^{O(\log\log{N})}$.

If one of the constructed algorithms ${\cal A}_{k}$ outputs matrices on inputs
$1^{N}$ infinitely often, then we are done, as we have a
$\mathsf{QP}^{\mathsf{NP}}$ algorithm outputting rigid matrices infinitely
often. Indeed, the algorithms ${\cal A}_{k}$ output only rigid matrices, and
the dimension of each such matrix is $M>2^{\delta_{0}n/12}=N^{\Theta(1)}$.

In the following, we assume that for each $k$, there exists $N_{k}$ such that
the algorithm ${\cal A}_{k}$ does not output matrices on inputs $1^{N}$ for
all $N\geq N_{k}$. Equivalently, there exists $n_{k}$ such that all $k$-SAT
formulas with $n\geq n_{k}$ variables and $cn$ clauses, when fed to the
reduction $R_{k}$, result in instances $(A_{i},B_{i})$ of
$\textrm{MM}_{\mathbb{F}_{q}}$ with $A_{i},B_{i}\in\mathbb{F}_{q}^{M\times M}$
either of size $M\leq 2^{\delta_{0}n/12}$ or satisfying

$\displaystyle{\mathcal{R}}_{M^{r(\gamma^{\prime})}}^{\mathbb{F}_{q}}(A_{i})<M^{s(\gamma^{\prime})}\text{\;\;
and
\;\;}{\mathcal{R}}_{M^{r(\gamma^{\prime})}}^{\mathbb{F}_{q}}(B_{i})<M^{s(\gamma^{\prime})}\;.$
(7)

We will use this to design a non-deterministic algorithm that solves $k$-TAUT
in time $O(2^{n(1-\delta_{0})})$ for every $k$, which refutes NSETH.

Given a $k$-DNF formula $\varphi$, we first apply the Sparsification Lemma to
(the negation of) $\varphi$ with $\lambda=\delta_{0}/4$. This gives us
$2^{\lambda n}$ $k$-CNF formulas $\varphi_{i}$ such that $\varphi$ is a
tautology if and only each $\varphi_{i}$ is unsatisfiable. Therefore, solving
$k$-TAUT for the negation of each $\varphi_{i}$ is sufficient for solving the
original instance $\varphi$. Now we apply the reduction $R_{k}$ to each
$\varphi_{i}$. Recall that the fine-grained reduction runs in time
$2^{(1-\delta_{0})n}$, and, in particular, creates at most
$2^{n(1-\delta_{0})}$ instances of MM, each of size at most
$2^{n(1-\delta_{0})}$. Therefore, the total number $T$ of instances of
$\textrm{MM}_{\mathbb{F}_{q}}$ we obtain is at most $T\leq 2^{\lambda n}\cdot
2^{n(1-\delta_{0})}=2^{(1-3\delta_{0}/4)n}$. We solve each instance of size
$M\leq 2^{\delta n/12}$ by a trivial cubic-time algorithm. The overall running
time to solve all such small instances is at most $T\cdot
2^{3\delta_{0}n/12}\leq 2^{n(1-\delta_{0}/2)}$.

Now we use the assumption that the algorithm ${\cal A}_{k}$ does not find
rigid matrices for all but finitely many inputs. Therefore, for every $n\geq
n_{k}$, every instance $(A_{i},B_{i})$, $A_{i},B_{i}\in\mathbb{F}^{M\times M}$
where $M>2^{\delta_{0}n/12}$ satisfies Equation 7. We apply Lemma 4.3 with
$\alpha=(\gamma-\gamma^{\prime})$ to compute $A_{i}\cdot B_{i}$ in non-
deterministic time
$M^{\gamma^{\prime}+\alpha}=M^{(\gamma+\gamma^{\prime})/2}=M^{\gamma(1-\varepsilon_{0})}$.
By the guarantee of the SETH-hardness reduction $R_{k}$, we have that a non-
deterministic algorithm solving $\textrm{MM}_{\mathbb{F}_{q}}$ in time
$M^{\gamma(1-\varepsilon_{0})}$ implies a non-deterministic algorithm for
$k$-TAUT with running time $2^{n(1-\delta_{0})}$. This refutes NSETH, and
finishes the proof of the theorem. ∎

###  4.3 Comparison with Known Rigidity Results

While the rigidity parameters that come out of $n^{\gamma}$-SETH-hardness of
matrix multiplication via Theorem 4.4 are not strong enough for Valiant’s
program for proving circuit lower bounds, they would improve on all currently
known constructions of rigid matrices. The main problem in this area is to
find an _explicit_ matrix (i.e., a matrix from a complexity class where we
cannot prove circuit lower bounds: $\mathsf{P},\mathsf{NP}$, or even
$\mathsf{E}^{\mathsf{NP}}$) of high rigidity for linear rank $r=\Theta(n)$.

The best known rigidity lower bound for matrices constructible in polynomial
time (i.e., from the class $\mathsf{P}$) is
${\mathcal{R}}_{r}^{\mathbb{F}}(A)\geq\Omega\left(\frac{n^{2}}{r}\cdot\log{\frac{n}{r}}\right)$
[Fri93, PR94, SSS97], and it falls short of achieving the rigidity parameters
needed for Valiant’s program (that requires rigidity
$\Omega(n^{1+\varepsilon})$ for $r=\Theta(n)$ for a constant $\varepsilon>0$).
Goldreich and Tal [GT16] give a matrix $A\in\mathbb{F}^{n\times n}$
constructible in time $2^{O(n)}$ (i.e., in the class $\mathsf{E}$) of rigidity
${\mathcal{R}}_{r}^{\mathbb{F}}(A)\geq\Omega\left(\frac{n^{3}}{r^{2}\log(n)}\right)$
for any $r\geq\sqrt{n}$, which improves on the previous constructions for
$r=o\left(\frac{n}{\log(n)\log\log(n)}\right)$. Alman and Chen, and Bhangale
et al. [AC19, BHPT20] give a matrix $A\in\mathbb{F}_{2}^{n\times n}$ achieving
very high rigidity ${\mathcal{R}}_{r}^{\mathbb{F}_{2}}(A)\geq\Omega(n^{2})$
for sub-polynomial rank $r=2^{\varepsilon\log(n)/\log\log(n)}$ in
$\mathsf{P}^{\mathsf{NP}}$.

We now compare the rigidity bounds implied by Theorem 4.4 from
$n^{\gamma}$-SETH-hardness for various values of $\gamma>2$ to the known lower
bounds on rigidity. For this, we use the bounds from Equations 5 and 6 and the
values of $\omega$ and $\omega^{\perp}$ from Equations 2 and 3. The rigidity
bound implied by Theorem 4.4 from $n^{\gamma}$-SETH-hardness for $\gamma\geq
2.37$ would give us a matrix $A$ of rigidity
${\mathcal{R}}_{r}^{\mathbb{F}}(A)\geq n^{1.68}$ for rank as high as
$r=n^{0.997}$. The rigidity bound obtained from $\gamma\geq 2.24$ would
improve upon the best known construction in $\mathsf{E}$ [GT16] for every
$r\geq n^{0.751}$. The rigidity bound obtained from any $\gamma\geq 2.17$
would already improve upon the best known constructions in $\mathsf{P}$
[Fri93, PR94, SSS97] for every $r\geq n^{0.63}$. Finally, the bound obtained
from any $\gamma\geq 2$ would give us rigidity for higher rank than the known
$\mathsf{P}^{\mathsf{NP}}$ constructions [AC19, BHPT20].

##  5 Reductions Between Variants of MMV

In this section, we describe variants of MMV and study their relative
difficulty compared to (standard) MMV and each other under deterministic
reductions using $O(n^{2})$ ring operations. (For clarity and conciseness, in
this section we assume that basic arithmetic operations over arbitrary rings
take constant time, and so refer to these reductions simply as $O(n^{2})$-time
deterministic operations.) See Figure 3 for a summary of these variants and
reductions between them.

MMVAllZeroesInverse-VerificationSymmetric-MMVStrong-Symmetric-
MMV${k}$-AllZeroesMono-All-Pairs-OV${k}$-MMVMPSMM Figure 3: A diagram of
reductions among MMV and related problems on $n\times n$ matrices. Arrows
represent deterministic $O(n^{2})$-time reductions (and double-headed arrows
denote equivalences under such reductions).  Red arrows indicate new (non-
trivial) reductions.

###  5.1 Problems Equivalent to MMV

In this section we present two problems (special cases of MMV) that are in
fact equivalent to (standard) MMV under deterministic $O(n^{2})$-time
reductions. These problems are: (1) the Inverse Verification Problem, and (2)
the Symmetric MMV problem.

####  5.1.1 Inverse Verification

It is known that matrix multiplication is $O(n^{2})$-time reducible to _matrix
inversion_ [BCS97, Proposition 16.6], and in fact that the problems are
equivalent under $O(n^{2})$-time reductions. Here we use a very similar
reduction to relate the verification analogs of these problems. We first
define the Inverse Verification Problem.

######  Definition 5.1 ($\text{Inverse-Verification}_{R}$).

The Inverse Verification Problem over a ring $R$ ($\text{Inverse-
Verification}_{R}$) is defined as follows. Given matrices $A,B\in R^{n\times
n}$ for some $n\in\mathbb{Z}^{+}$ as input, decide whether $B=A^{-1}$.

We next give the reduction.

######  Theorem 5.2.

For any ring $R$, there is an $O(n^{2})$-time reduction from
$\text{AllZeroes}_{R}$ on $n\times n$ matrices to $\text{Inverse-
Verification}_{R}$ on $3n\times 3n$ matrices.

###### Proof.

Let $A,B\in R^{n\times n}$ be the input instance of $\text{AllZeroes}_{R}$,
and define the block matrices

$A^{\prime}=\begin{bmatrix}I&A&0\\\ 0&I&B\\\ 0&0&I\end{bmatrix},\ \ \ \
B^{\prime}=\begin{bmatrix}I&-A&0\\\ 0&I&-B\\\ 0&0&I\end{bmatrix}\ \text{.}$

It is straightforward to check that

$A^{\prime}B^{\prime}=\begin{bmatrix}I&0&-AB\\\ 0&I&0\\\ 0&0&I\end{bmatrix}\
\text{,}$

and so $A^{\prime}B^{\prime}=I_{3n}$ if and only if $AB=0$. ∎

####  5.1.2 Symmetric MMV

Inverse-Verification is not the only variant (special case) of MMV that is
equivalent to MMV. Suppose that the input matrices $A$ and $B$ in an MMV
instance are symmetric. One might hope this would make MMV easier, however we
next show that this is not the case.

######  Definition 5.3 ($\text{Symmetric-MMV}_{R}$).

The Symmetric Matrix Multiplication Verification Problem over a ring $R$
($\text{Symmetric-MMV}_{R}$) is defined as follows. Given symmetric matrices
$A,B\in R^{n\times n}$ and a matrix $C\in R^{n\times n}$ for some
$n\in\mathbb{Z}^{+}$ as input, decide whether $AB=C$.

Note that this definition does not require that $C$ be a symmetric matrix.

######  Theorem 5.4.

For any ring $R$, there is an $O(n^{2})$-time reduction from $\text{MMV}_{R}$
on $n\times n$ matrices to $\text{Symmetric-MMV}_{R}$ on $3n\times 3n$
matrices.

###### Proof.

Let $A,B,C\in R^{n\times n}$ be the input instance of $\text{MMV}_{R}$, and
define matrices $A^{\prime},B^{\prime},C^{\prime}$ as follows:

$A^{\prime}=\begin{bmatrix}I&0&A\\\ 0&I&-A\\\
A^{T}&-A^{T}&I\end{bmatrix},\quad B^{\prime}=\begin{bmatrix}I&0&B^{T}\\\
0&I&B^{T}\\\ B&B&I\end{bmatrix},\quad
C^{\prime}=\begin{bmatrix}I+C&C&B^{T}+A\\\ -C&I-C&B^{T}-A\\\
A^{T}+B&-A^{T}+B&I\end{bmatrix}\ \text{.}$

It is easy to check that $A^{\prime}$ and $B^{\prime}$ are both symmetric,
and, because adding and taking the tranpose of $n\times n$ matrices takes
$O(n^{2})$ time, $A^{\prime},B^{\prime},C^{\prime}$ are all computable in
$O(n^{2})$ time.

Moreover, it is easy to check that

$A^{\prime}B^{\prime}=\begin{bmatrix}I+AB&AB&B^{T}+A\\\ -AB&I-AB&B^{T}-A\\\
A^{T}+B&-A^{T}+B&I\end{bmatrix}\ \text{,}$

and hence that $A^{\prime}B^{\prime}=C^{\prime}$ if and only if $AB=C$. ∎

###  5.2 Problems no Harder than MMV

Next, in this section, we present two problems that are $O(n^{2})$-time
reducible to MMV, but that are not obviously equivalent to MMV and are not
obviously solvable in less time than MMV. The problems are: (1) the
Monochromatic All-Pairs Orthogonal Vectors Problem, and (2) the Strong
Symmetric MMV Problem. We propose these problems (as special cases of MMV) as
good targets for making algorithmic progress on MMV.

####  5.2.1 Monochromatic All Pairs Orthogonal Vectors

######  Definition 5.5 ($\text{Monochromatic-All-Pairs-OV}_{R}$).

The Monochromatic All Pairs Orthogonal Vectors Problem over a ring $R$
($\text{Monochromatic-All-Pairs-OV}_{R}$) is defined as follows. Given vectors
$\boldsymbol{a}_{1},\ldots,\boldsymbol{a}_{n}\in R^{n}$ for some
$n\in\mathbb{Z}^{+}$, decide whether for all $i,j\in[n],i\neq j$,
$\langle\boldsymbol{a}_{i},\boldsymbol{a}_{j}\rangle=0$.

We next show that Monochromatic-All-Pairs-OV reduces to
$\text{MMV}_{\mathbb{Z}}$.

######  Lemma 5.6.

There is a $O(n^{2})$-time reduction from $\text{Monochromatic-All-Pairs-
OV}_{R}$ on $n$ vectors of length $n$ to $\text{MMV}_{R}$ on $n\times n$
matrices.

###### Proof.

Let $\boldsymbol{a}_{1},\ldots,\boldsymbol{a}_{n}\in R^{n}$ be the input
instance of Monochromatic-All-Pairs-OV, and define
$A:=(\boldsymbol{a}_{1},\ldots,\boldsymbol{a}_{n})\in R^{n\times n}$.
Additionally, compute

$C=\operatorname{diag}(\langle\boldsymbol{a}_{1},\boldsymbol{a}_{1}\rangle,\langle\boldsymbol{a}_{2},\boldsymbol{a}_{2}\rangle,\ldots,\langle\boldsymbol{a}_{n},\boldsymbol{a}_{n}\rangle)=\begin{bmatrix}\langle\boldsymbol{a}_{1},\boldsymbol{a}_{1}\rangle&0&\cdots&0\\\
0&\langle\boldsymbol{a}_{2},\boldsymbol{a}_{2}\rangle&\cdots&0\\\
\vdots&\vdots&\ddots&0\\\
0&0&\cdots&\langle\boldsymbol{a}_{n},\boldsymbol{a}_{n}\rangle\end{bmatrix}\
\text{,}$

and output the $\text{MMV}_{R}$ instance $A^{T},A,C$. It is straightforward to
check that $A^{T}A=C$ if and only if for all $i,j\in[n],i\neq j$,
$\langle\boldsymbol{a}_{i},\boldsymbol{a}_{j}\rangle=0$. Moreover, computing
each of $A$, $A^{T}$, and $C$ requires $O(n^{2})$ time, as needed. ∎

We note that, interestingly, while it is relatively straightforward to reduce
$\text{Monochromatic-All-Pairs-OV}_{R}$ to $\text{MMV}_{R}$ in $O(n^{2})$
time, it is not clear that such a reduction in the other direction exists. In
contrast, the bichromatic analogue of Monochromatic-All-Pairs-OV (in which
given
$\boldsymbol{a}_{1},\ldots,\boldsymbol{a}_{n},\boldsymbol{b}_{1},\ldots,\boldsymbol{b}_{n}$
the goal is to decide whether
$\langle\boldsymbol{a}_{i},\boldsymbol{b}_{j}\rangle=0$ for all $1\leq i,j\leq
n$) is equivalent to AllZeroes.

####  5.2.2 Strong Symmetric MMV

For our second problem that is no harder than MMV, we consider the special
case of Symmetric-MMV when $C$ must also be symmetric. We call this problem
Strong-Symmetric-MMV and define it as follows.

######  Definition 5.7 ($\text{Strong-Symmetric-MMV}_{R}$).

The Strong Symmetric Matrix Multiplication Verification Problem over a ring
$R$ ($\text{Strong-Symmetric-MMV}_{R}$) is defined as follows. Given symmetric
matrices $A,B,C\in R^{n\times n}$ for some $n\in\mathbb{Z}^{+}$ as input,
decide whether $AB=C$.

We note that the reduction in Theorem 5.4 does _not_ work as a reduction to
Strong-Symmetric-MMV. On the other hand, it is not clear how to solve Strong-
Symmetric-MMV more efficiently than MMV. However, finding faster algorithms
for Strong-Symmetric-MMV seems like a good starting point for finding faster
algorithms for general MMV.

We make several structural observations to this end. First, we note that the
product of two symmetric matrices is itself symmetric if and only if the two
matrices commute. That is, for symmetric matrices $A$ and $B$, $AB=(AB)^{T}$
if and only if $AB=BA$. Second, since symmetric matrices (over a field
$\mathbb{F}$) are always diagonalizable, we know that two diagonalizable
matrices commute if and only if they are simultaneously diagonalizable (see
[HJ12, Theorem 1.3.21]).101010We say that matrices $A,B\in\mathbb{F}^{n\times
n}$ are simultaneously diagonalizable if there exists some matrix
$P\in\mathbb{F}^{n\times n}$ such that $PAP^{-1}$ and $PBP^{-1}$ are both
diagonal matrices.

While it seems like it may be possible to exploit these properties to find a
faster algorithm, there are some caveats. The added restriction that $C$ is
symmetric still does not guarantee that $AB$ is itself symmetric, meaning the
above properties ($A$ and $B$ commuting and being simultaneously
diagonalizable) are not guaranteed, so we cannot assume them to be true. That
is, if $AB$ is symmetric and therefore $A$ and $B$ commute and are
simultaneously diagonalizable, it does not guarantee that $AB=C$. So, although
these observations about symmetric matrices $A$ and $B$ may be useful, they do
not obviously lead to a faster algorithm for Strong-Symmetric-MMV.

###  5.3 Problems at Least as Hard as MMV but no Harder than MM

Finally, we present two problems to which MMV is deterministically
$O(n^{2})$-time reducible, and that are deterministically $O(n^{2})$-time
reducible to MM. These problems are: (1) the $k$-MMV problem, and (2) the
Matrix Product Sparsity Problem (MPS). We also present the $k$-AllZeroes
problem, and show that it is equivalent to $k$-MMV.

####  5.3.1 Generalized AllZeroes Equivalence

So far, we have only discussed verifying the product of _two_ matrices. But,
it is also natural to ask about the complexity of verifying the product of
$k>2$ matrices. Accordingly, we define the following problems.

######  Definition 5.8 (k$\text{-MMV}_{R}$).

Let $k\geq 2$ be a fixed integer. The $k$-Matrix Multiplication Verification
Problem over a ring $R$ (k$\text{-MMV}_{R}$) is defined as follows. Given
matrices $A_{1},\ldots,A_{k},C\in R^{n\times n}$ for some $n\in\mathbb{Z}^{+}$
as input, decide whether $\prod_{i=1}^{k}A_{i}=C$.

######  Definition 5.9 (k$\text{-AllZeroes}_{R}$).

Let $k\geq 2$ be a fixed integer. The $k$-All Zeroes Problem over a ring $R$
(k$\text{-AllZeroes}_{R}$) is defined as follows. Given matrices
$A_{1},\ldots,A_{k}\in R^{n\times n}$ for some $n\in\mathbb{Z}^{+}$ as input,
decide whether $\prod_{i=1}^{k}A_{i}=0$.

We note that $2$-$\text{MMV}_{R}$ and $2$-$\text{AllZeroes}_{R}$ are
“standard” $\text{MMV}_{R}$ and $\text{AllZeroes}_{R}$, respectively.

It turns out that many algorithms (including ours) for MMV also work for
$k$-MMV, and in fact we can generalize certain results about the complexity of
MMV. Additionally, it is easy to reduce MMV to $k$-MMV for any $k\geq 2$, but
the reduction in the opposite direction is unclear. We first show that $k$-MMV
and $k$-AllZeroes are equivalent.

######  Theorem 5.10.

Let $k$ be some fixed positive integer, and let $R$ be a ring. There is a
$O(n^{2})$-time reduction from $k$-$\text{MMV}_{R}$ on $n\times n$ matrices to
$k$-$\text{AllZeroes}_{R}$ on $2n\times 2n$ matrices.

###### Proof.

Let $A_{1},\ldots,A_{n},C\in R^{n\times n}$ be the input instance of
$k$-$\text{MMV}_{R}$. We output

$\displaystyle A_{1}^{\prime}$ $\displaystyle:=\begin{bmatrix}A_{1}&I\\\
0&0\end{bmatrix}\ \text{,}$ $\displaystyle A_{i}^{\prime}$
$\displaystyle:=\begin{bmatrix}A_{i}&I\\\ 0&0\end{bmatrix}\text{ for $1<i<k$,
and}$ $\displaystyle A_{k}^{\prime}$ $\displaystyle:=\begin{bmatrix}A_{k}&0\\\
-C&0\end{bmatrix}$

as our $k$-$\text{AllZeroes}_{R}$ instance.

Note that

$\prod_{i=1}^{k}A_{i}^{\prime}=\begin{bmatrix}A_{1}&I\\\
0&0\end{bmatrix}\cdot\prod_{i=2}^{k-1}\begin{bmatrix}A_{i}&0\\\
0&I\end{bmatrix}\cdot\begin{bmatrix}A_{k}&0\\\
-C&0\end{bmatrix}=\begin{bmatrix}\prod_{i=1}^{k}A_{i}-C&0\\\ 0&0\end{bmatrix}\
\text{,}$

and that this product equals the all-zeroes matrix if and only if
$\prod_{i=1}^{k}A_{i}=C$. ∎

We also note that the reduction in the other direction (from
$k$-$\text{AllZeroes}_{R}$ to $k$-$\text{MMV}_{R}$) follows immediately by
setting $C=0$.

####  5.3.2 Relation to Orthogonal Vectors and Matrix-Product-Sparsity

We noted previously how both the monochromatic and bichromatic versions of
All-Pairs-OV reduce to MMV, and how the bichromatic version is equivalent to
AllZeroes. However, essentially all variations of Orthogonal Vectors can be
generalized by the (monochromatic or bichromatic) _counting version_ of the
Orthogonal Vectors Problem (#OV), in which the goal is to decide whether the
number of orthogonal pairs is less than or equal to an input parameter $t$. It
is natural then to study how #OV is related to MMV. To do so, we introduce an
equivalent matrix formulation of #OV that we call the _Matrix Product Sparsity
Problem_ , the goal of which is to decide whether $\lVert AB\rVert_{0}\leq t$
for some input matrices $A,B$ and number $t$.

######  Definition 5.11 ($\text{MPS}_{R}$).

The Matrix Product Sparsity Problem over a ring $R$ ($\text{MPS}_{R}$) is
defined as follows. Given matrices $A,B\in R^{n\times n}$ for some
$n\in\mathbb{Z}^{+}$ and $t\in\mathbb{Z}^{+}$ as input, decide whether $\lVert
AB\rVert_{0}\leq t$.

It immediately follows that MPS is intermediate in difficulty to MMV and MM.

######  Lemma 5.12.

Let $R$ be a ring. There is an $O(n^{2})$-time reduction from $\text{MMV}_{R}$
on $n\times n$ matrices to $\text{MPS}_{R}$ on $n\times n$ matrices, and from
$\text{MPS}_{R}$ on $n\times n$ matrices to $\text{MM}_{R}$ on $n\times n$
matrices.

###### Proof.

The reduction from $\text{MMV}_{R}$ goes through $\text{AllZeroes}_{R}$, to
which $\text{MMV}_{R}$ is equivalent. Indeed, $\text{AllZeroes}_{R}$ is the
special case of $\text{MPS}_{R}$ when $t=0$. For the reduction from
$\text{MPS}_{R}$ to $\text{MM}_{R}$, given an instance $A,B,t$ of
$\text{MPS}_{R}$ as input, compute $AB$ and then count the number of non-zero
entries in $AB$ in $O(n^{2})$ time. ∎

## References

  * [ABB+23] Divesh Aggarwal, Huck Bennett, Zvika Brakerski, Alexander Golovnev, Rajendra Kumar, Zeyong Li, Spencer Peters, Noah Stephens-Davidowitz, and Vinod Vaikuntanathan.  Lattice problems beyond polynomial time.  In STOC, 2023.
  * [ABFK23] Amir Abboud, Karl Bringmann, Nick Fischer, and Marvin Künnemann.  The time complexity of fully sparse matrix multiplication.  arxiv:2309.06317, 2023.
  * [AC19] Josh Alman and Lijie Chen.  Efficient construction of rigid matrices using an NP oracle.  In FOCS, 2019.
  * [AGHP90] Noga Alon, Oded Goldreich, Johan Håstad, and René Peralta.  Simple construction of almost $k$-wise independent random variables.  In FOCS, 1990.
  * [AV21] Joah Alman and Virginia Vassilevska Williams.  A refined laser method and faster matrix multiplication.  In SODA, 2021.
  * [BCS97] Peter Bürgisser, Michael Clausen, and Amin Shokrollahi.  Algebraic Complexity Theory, volume 315.  Springer, 1997.
  * [BGK+23] Tatiana Belova, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin, and Denil Sharipov.  Polynomial formulations as a barrier for reduction-based hardness proofs.  In SODA, 2023.
  * [BHPT20] Amey Bhangale, Prahladh Harsha, Orr Paradise, and Avishay Tal.  Rigid matrices from rectangular PCPs or: Hard claims have complex proofs.  In FOCS, 2020.
  * [BKM+23] Tatiana Belova, Alexander S. Kulikov, Ivan Mihajlin, Olga Ratseeva, Grigory Reznikov, and Denil Sharipov.  Computations with polynomial evaluation oracle: ruling out superlinear SETH-based lower bounds.  arXiv:2307.11444, 2023.
  * [BS04] Harry Buhrman and Robert Spalek.  Quantum verification of matrix products.  arXiv:quant-ph/0409035, 2004.
  * [CGI+16] Marco L. Carmosino, Jiawei Gao, Russell Impagliazzo, Ivan Mihajlin, Ramamohan Paturi, and Stefan Schneider.  Nondeterministic extensions of the strong exponential time hypothesis and consequences for non-reducibility.  In ITCS, 2016.
  * [CKSU05] Henry Cohn, Robert Kleinberg, Balázs Szegedy, and Christopher Umans.  Group-theoretic algorithms for matrix multiplication.  In FOCS, 2005.
  * [DWZ23] Ran Duan, Hongxun Wu, and Renfei Zhou.  Faster matrix multiplication via asymmetric hashing.  In FOCS, 2023.
  * [Fre79] Rūsiņš Freivalds.  Fast probabilistic algorithms.  In MFCS, 1979.
  * [Fri93] Joel Friedman.  A note on matrix rigidity.  Combinatorica, 13:235–239, 1993.
  * [GLL+17] Leszek Gasieniec, Christos Levcopoulos, Andrzej Lingas, Rasmus Pagh, and Takeshi Tokuyama.  Efficiently correcting matrix products.  Algorithmica, 79(2):428–443, 2017.
  * [GRS22] Venkatesan Guruswami, Atri Rudra, and Madhu Sudan.  Essential Coding Theory.  Online Draft, 2022.
  * [GT16] Oded Goldreich and Avishay Tal.  Matrix rigidity of random Toeplitz matrices.  In STOC, 2016.
  * [Hal] Jonathan I. Hall.  Notes on coding theory.  Available at https://users.math.msu.edu/users/halljo/classes/codenotes/GRS.pdf.
  * [HJ12] Roger A. Horn and Charles R. Johnson.  Matrix Analysis.  Cambridge University Press, 2012.
  * [HTW23] Wing-Kai Hon, Meng-Tsung Tsai, and Hung-Lung Wang.  Verifying the product of generalized boolean matrix multiplication and its applications to detect small subgraphs.  In WADS, 2023.
  * [IP99] Russell Impagliazzo and Ramamohan Paturi.  The complexity of $k$-SAT.  In CCC, 1999.
  * [IPZ98] Russell Impagliazzo, Ramamohan Paturi, and Francis Zane.  Which problems have strongly exponential complexity?  In FOCS, 1998.
  * [IS09] Mark A. Iwen and Craig V. Spencer.  A note on compressed sensing and the complexity of matrix multiplication.  Information Processing Letters, 109(10):468–471, 2009.
  * [Iwe23] Mark A. Iwen, 2023.  Personal Communication.
  * [JMV15] Hamid Jahanjou, Eric Miles, and Emanuele Viola.  Local reductions.  In ICALP, 2015.
  * [KS93] Tracy Kimbrel and Rakesh Kumar Sinha.  A probabilistic algorithm for verifying matrix products using $O(n^{2})$ time and $\log_{2}n+O(1)$ random bits.  Information Processing Letters, 45(2):107–110, 1993.
  * [Kün18] Marvin Künnemann.  On nondeterministic derandomization of Freivalds’ algorithm: Consequences, avenues and algorithmic progress.  In ESA, 2018.
  * [KW14] Ivan Korec and Jiří Wiedermann.  Deterministic verification of integer matrix multiplication in quadratic time.  In SOFSEM, 2014.
  * [LG12] François Le Gall.  Faster algorithms for rectangular matrix multiplication.  In FOCS, 2012.
  * [LG23] François Le Gall.  Faster rectangular matrix multiplication by combination loss analysis.  arXiv:2307.06535, 2023.
  * [LR83] Grazia Lotti and Francesco Romani.  On the asymptotic complexity of rectangular matrix multiplication.  Theoretical Computer Science, 23(2):171–185, 1983.
  * [LU18] François Le Gall and Florent Urrutia.  Improved rectangular matrix multiplication using powers of the Coppersmith-Winograd tensor.  In SODA, 2018.
  * [PR94] Pavel Pudlák and Vojtech Rödl.  Some combinatorial-algebraic problems from complexity theory.  Discrete Mathematics, 1(136):253–279, 1994.
  * [PS72] George Pólya and Gabor Szegö.  Problems and Theorems in Analysis: Series, integral calculus, theory of functions.  Springer, 1972.
  * [RL89] Ron M. Roth and Abraham Lempel.  On MDS codes via Cauchy matrices.  IEEE Transactions on Information Theory, 35(6):1314–1319, 1989\.
  * [Sho90] Victor Shoup.  New algorithms for finding irreducible polynomials over finite fields.  Mathematics of computation, 54(189):435–447, 1990.
  * [Sho09] Victor Shoup.  A computational introduction to number theory and algebra.  Cambridge University Press, 2009.
  * [SSS97] Mohammad Amin Shokrollahi, Daniel A. Spielman, and Volker Stemann.  A remark on matrix rigidity.  Information Processing Letters, 64(6):283–285, 1997.
  * [Val77] Leslie G. Valiant.  Graph-theoretic arguments in low-level complexity.  In MFCS, 1977.
  * [Vas15] Virginia Vassilevska Williams.  Hardness of easy problems: Basing hardness on popular conjectures such as the strong exponential time hypothesis (invited talk).  In IPEC, 2015.
  * [Vas18] Virginia Vassilevska Williams.  On some fine-grained questions in algorithms and complexity.  In ICM, 2018.
  * [VXXZ23] Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, and Renfei Zhou.  New bounds for matrix multiplication: from alpha to omega.  arXiv:2307.07970, 2023.
  * [vzGG13] Joachim von zur Gathen and Jürgen Gerhard.  Modern Computer Algebra.  Cambridge University Press, 3 edition, 2013.
  * [WW23] Yu-Lun Wu and Hung-Lung Wang.  Correcting matrix products over the ring of integers.  arxiv:2307.12513, 2023.
  * [YZ05] Raphael Yuster and Uri Zwick.  Fast sparse matrix multiplication.  ACM Transactions On Algorithms, 1(1):2–13, 2005.
  * [Zwi02] Uri Zwick.  All pairs shortest paths using bridging sets and rectangular matrix multiplication.  Journal of the ACM, 49(3):289–317, 2002.