2021/02/10 by Dori Medini, Medini, Dori, Shpilka, Amir
Computer Science · Engineering · #Advanced Memory and Neural Computing #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Quantum Computing Algorithms and Architecture
paper · pdf · doi:10.48550/arxiv.2102.05632
openalex publication_date 2021/02/10 · openalex created_date 2024/04/11 · openalex updated_date 2026/07/31
In this paper we study polynomials in VPe (polynomial-sized formulas) and in ΣΠΣ (polynomial-size depth-3 circuits) whose orbits, under the action of the affine group GLnaff(\mathbbF), are dense in their ambient class. We construct hitting sets and interpolating sets for these orbits as well as give reconstruction algorithms. As VP=VNC2, our results for VPe 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.