Small hitting-sets for tiny arithmetic circuits or: How to turn bad designs into good

Manindra Agrawal, Michael Forbes, Sumanta Ghosh +1

We show that if we can design poly($s$)-time hitting-sets for $\Sigma {\wedge }^a\Sigma {\Pi }^{O(\log s)}$ circuits of size $s$, where $a=\omega (1)$ is arbitrarily small and the number of variables, or ar…