Hitting Sets and Reconstruction for Dense Orbits in ${\text{VP}}_e$ and $\Sigma \Pi \Sigma$ Circuits

Abstract

In this paper we study polynomials in ${\text{VP}}_e$ (polynomial-sized formulas) and in $\Sigma \Pi \Sigma$ (polynomial-size depth-$3$ circuits) whose orbits, under the action of the affine group ${\text{GL}}_n^{\text{aff}}(\mathbb{F})$, are $dense$ in their ambient class. We construct hitting sets and interpolating sets for these orbits as well as give reconstruction algorithms. As $\text{VP}={\text{VNC}}^2$, our results for ${\text{VP}}_e$ translate immediately to $\text{VP}$ with a quasipolynomial blow up in parameters. If any of our hitting or interpolating sets could be made $robust$ then this would immediately yield a hitting set for the superclass in which the relevant class is dense, and as a consequence also a lower bound for the superclass. Unfortunately, we also prove that the kind of constructions that we have found (which are defined in terms of $k$-independent polynomial maps) do not necessarily yield robust hitting sets.