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 $\omega$ is not 2, our generator has seed length $O(n^{1-\epsilon })$ and hits circuits of size $O(n^{1+\delta })$ for sufficiently small $\epsilon ,\delta >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.

References in corpus (6)

• Group-theoretic algorithms for matrix multiplication
• On cap sets and the group-theoretic approach to matrix multiplication
• A group-theoretic approach to fast matrix multiplication
• Fast Matrix Multiplication: Limitations of the Laser Method
• The Complexity of Factors of Multivariate Polynomials
• Ideals, Determinants, and Straightening: Proving and Using Lower Bounds for Polynomial Ideals