On Matrix Multiplication and Polynomial Identity Testing
Robert Andrews · SIAM Journal on Computing · 2024
Abstract. We show that lower bounds on the border rank of matrix multiplication can be used to nontrivially derandomize polynomial identity testing for small algebraic circuits. Letting [Formula: see text] denote the border rank of [Formula: see text] matrix multiplication, we construct a hitting set generator with seed length [Formula: see text] that hits [Formula: see text]-variate circuits of multiplicative complexity [Formula: see text]. If the matrix multiplication exponent [Formula: see text] is not 2, our generator has seed length [Formula: see text] and hits circuits of size [Formula: see text] for sufficiently small [Formula: see text]. Surprisingly, the fact that [Formula: see text] already yields new, nontrivial hitting set generators for circuits of sublinear multiplicative complexity.