All reports by Author Dori Medini:

__
TR21-014
| 15th February 2021
__

Dori Medini, Amir Shpilka#### Hitting Sets and Reconstruction for Dense Orbits in VP$_e$ and $\Sigma\Pi\Sigma$ Circuits

Dori Medini, Amir Shpilka

In this paper we study polynomials in VP$_e$ (polynomial-sized formulas) and in $\Sigma\Pi\Sigma$ (polynomial-size depth-$3$ circuits) whose orbits, under the action of the affine group GL$^{aff}_n({\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 ... more >>>