# On Matrix Multiplication and Polynomial Identity Testing

Preprint · Robert Andrews

- Archive id: arxiv:2208.01078
- Published: 2022-08-01
- DOI: https://doi.org/10.1109/focs54457.2022.00041,10.1137/22m1536169
- arXiv: https://arxiv.org/abs/2208.01078
- Source URL: https://arxiv.org/abs/2208.01078
- PDF: https://arxiv.org/pdf/2208.01078
- Provenance: arxiv

## 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 reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.