On Matrix Multiplication and Polynomial Identity Testing

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{\text{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}.\underline{\text{R}}^{-1}(s))$ that hits n-variate circuits of multiplicative complexity s. If the matrix multiplication exponent w is not 2, our generator has seed length $O(n^{1-\varepsilon})$ and hits circuits of size $O(n^{1+\delta})$ for sufficiently small $\varepsilon, \delta\gt 0$. Surprisingly, the fact that $\underline{\text{R}}(n)\geq n^{2}$ already yields new, non-trivial hitting set generators for circuits of sublinear multiplicative complexity.