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

Dori Medini, Amir Shpilka

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…