Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR21-014 | 15th February 2021 10:58

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


Authors: Dori Medini, Amir Shpilka
Publication: 15th February 2021 10:59
Downloads: 436


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 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.

ISSN 1433-8092 | Imprint