We prove that hashing $n$ balls into $n$ bins via a random matrix over $GF(2)$ yields expected maximum load $O(\log n / \log \log n)$. This matches the expected maximum load of a fully random function and resolves an open question posed by Alon, Dietzfelbinger, Miltersen, Petrank, and Tardos (STOC ... 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 >>>

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