On Matrix Multiplication and Polynomial Identity Testing
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2022
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909171774914560 |
|---|---|
| author | Andrews, Robert |
| author_facet | Andrews, Robert |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2208_01078 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | On Matrix Multiplication and Polynomial Identity Testing Andrews, Robert Computational Complexity 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. |
| title | On Matrix Multiplication and Polynomial Identity Testing |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2208.01078 |