Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

Paper:

TR21-014 | 15th February 2021 10:58

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

TR21-014
Authors: Dori Medini, Amir Shpilka
Publication: 15th February 2021 10:59
Keywords:

Abstract:

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