hide
Free keywords:
Computer Science, Data Structures and Algorithms, cs.DS,Computer Science, Computational Complexity, cs.CC
Abstract:
Motivated by studying the power of randomness, certifying algorithms and
barriers for fine-grained reductions, we investigate the question whether the
multiplication of two $n\times n$ matrices can be performed in near-optimal
nondeterministic time $\tilde{O}(n^2)$. Since a classic algorithm due to
Freivalds verifies correctness of matrix products probabilistically in time
$O(n^2)$, our question is a relaxation of the open problem of derandomizing
Freivalds' algorithm.
We discuss consequences of a positive or negative resolution of this problem
and provide potential avenues towards resolving it. Particularly, we show that
sufficiently fast deterministic verifiers for 3SUM or univariate polynomial
identity testing yield faster deterministic verifiers for matrix
multiplication. Furthermore, we present the partial algorithmic progress that
distinguishing whether an integer matrix product is correct or contains between
1 and $n$ erroneous entries can be performed in time $\tilde{O}(n^2)$ --
interestingly, the difficult case of deterministic matrix product verification
is not a problem of "finding a needle in the haystack", but rather cancellation
effects in the presence of many errors.
Our main technical contribution is a deterministic algorithm that corrects an
integer matrix product containing at most $t$ errors in time
$\tilde{O}(\sqrt{t} n^2 + t^2)$. To obtain this result, we show how to compute
an integer matrix product with at most $t$ nonzeroes in the same running time.
This improves upon known deterministic output-sensitive integer matrix
multiplication algorithms for $t = \Omega(n^{2/3})$ nonzeroes, which is of
independent interest.
