We give upper and lower bounds on the power of subsystems of the Ideal Proof System (IPS), the algebraic proof system recently proposed by Grochow and Pitassi, where the circuits comprising the proof come from various restricted algebraic circuit classes. This mimics an established research direction in the ... more >>>

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

We study the arithmetic complexity of hitting set generators, which are pseudorandom objects used for derandomization of the polynomial identity testing problem. We give new explicit constructions of hitting set generators whose outputs are computable in $VNC^0$, i.e., can be computed by arithmetic formulas of constant size. Unconditionally, we construct ... more >>>