All reports by Author Robert Andrews:

__
TR24-080
| 16th April 2024
__

Robert Andrews, Avi Wigderson#### Constant-Depth Arithmetic Circuits for Linear Algebra Problems

__
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, Avi Wigderson

We design polynomial size, constant depth (namely, $AC^0$) arithmetic formulae for the greatest common divisor (GCD) of two polynomials, as well as the related problems of the discriminant, resultant, Bézout coefficients, squarefree decomposition, and the inversion of structured matrices like Sylvester and Bézout matrices. Our GCD algorithm extends to any ... more >>>

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