ECCC-Report TR21-014https://eccc.weizmann.ac.il/report/2021/014Comments and Revisions published for TR21-014en-usMon, 15 Feb 2021 10:59:08 +0200
Paper TR21-014
| Hitting Sets and Reconstruction for Dense Orbits in VP$_e$ and $\Sigma\Pi\Sigma$ Circuits |
Dori Medini,
Amir Shpilka
https://eccc.weizmann.ac.il/report/2021/014In 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 VP$=$VNC$^2$, our results for VP$_e$ translate immediately to 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.
Mon, 15 Feb 2021 10:59:08 +0200https://eccc.weizmann.ac.il/report/2021/014