All reports by Author Robert Andrews:

__
TR22-111
| 1st August 2022
__

Robert Andrews#### On Matrix Multiplication and Polynomial Identity Testing

__
TR21-172
| 1st December 2021
__

Robert Andrews, Michael Forbes#### Ideals, Determinants, and Straightening: Proving and Using Lower Bounds for Polynomial Ideals

__
TR20-081
| 21st May 2020
__

Robert Andrews#### Algebraic Hardness versus Randomness in Low Characteristic

Robert Andrews

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 ... more >>>

Robert Andrews, Michael Forbes

We show that any nonzero polynomial in the ideal generated by the $r \times r$ minors of an $n \times n$ matrix $X$ can be used to efficiently approximate the determinant. Specifically, for any nonzero polynomial $f$ in this ideal, we construct a small depth-three $f$-oracle circuit that approximates the ... more >>>

Robert Andrews

We show that lower bounds for explicit constant-variate polynomials over fields of characteristic $p > 0$ are sufficient to derandomize polynomial identity testing over fields of characteristic $p$. In this setting, existing work on hardness-randomness tradeoffs for polynomial identity testing requires either the characteristic to be sufficiently large or the ... more >>>