On Matrix Multiplication and Polynomial Identity Testing

Abstract

We show that lower bounds on the border rank of matrix multiplication can be used to non-trivially derandomize polynomial identity testing for small algebraic circuits. Letting $\underline{R}(n)$ denote the border rank of $n \times n \times n$ matrix multiplication, we construct a hitting set generator with seed length $O(\sqrt{n} \cdot \underline{R}^{-1}(s))$ that hits $n$-variate circuits of multiplicative complexity $s$. If the matrix multiplication exponent $ω$ is not 2, our generator has seed length $O(n^{1 - \varepsilon})$ and hits circuits of size $O(n^{1 + δ})$ for sufficiently small $\varepsilon, δ> 0$. Surprisingly, the fact that $\underline{R}(n) \ge n^2$ already yields new, non-trivial hitting set generators for circuits of sublinear multiplicative complexity.

Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv.