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

We investigate the consequences of the existence of ``efficiently describable'' hitting sets for polynomial sized algebraic circuit (VP), in particular, \emph{VP-succinct hitting sets}.
Existence of such hitting sets is known to be equivalent to a ``natural-proofs-barrier'' towards algebraic circuit lower bounds, from the works that introduced this concept (Forbes ... more >>>

We design the first efficient polynomial identity testing algorithms over the nonassociative polynomial algebra. In particular, multiplication among the formal variables is commutative but it is not associative. This complements the strong lower bound results obtained over this algebra by Hrubeš, Yehudayoff, and Wigderson (CCC 2010) and Fijalkow, Lagarde, Ohlmann, ... more >>>