Hitting sets and reconstruction for dense orbits in VPe and ΣΠΣ circuits

DOI10.4230/LIPICS.CCC.2021.19arXiv2102.05632OpenAlexW3135265635MaRDI QIDQ6115375

Author name not available (Why is that?), Amir Shpilka

Publication date: 12 July 2023

Abstract: In this paper we study polynomials in

e x t {V P}_{e}

(polynomial-sized formulas) and in

S i g m a P i S i g m a

(polynomial-size depth-

3

circuits) whose orbits, under the action of the affine group

e x t {G L}_{n}^{e x t a f f} (m a t h b b F)

, are

m a t h i t d e n s e

in their ambient class. We construct hitting sets and interpolating sets for these orbits as well as give reconstruction algorithms. As

e x t V P = e x t {V N C}^{2}

, our results for

e x t {V P}_{e}

translate immediately to

e x t V P

with a quasipolynomial blow up in parameters. If any of our hitting or interpolating sets could be made

m a t h i t r o b u s t

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.

Full work available at URL: https://arxiv.org/abs/2102.05632

zbMATH Keywords

algebraic complexity algebraic circuits VP VNP algebraic formula

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

This page was built for publication: Hitting sets and reconstruction for dense orbits in VPe and ΣΠΣ circuits

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6115375)