License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CCC.2021.19
URN: urn:nbn:de:0030-drops-142930
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14293/
Medini, Dori ;
Shpilka, Amir
Hitting Sets and Reconstruction for Dense Orbits in VP_{e} and ΣΠΣ Circuits
Abstract
In this paper we study polynomials in VP_{e} (polynomial-sized formulas) and in ΣΠΣ (polynomial-size depth-3 circuits) whose orbits, under the action of the affine group GL^{aff}_n(?) (the action of (A,b) ∈ GL^{aff}_n(?) on a polynomial f ∈ ?[x] is defined as (A,b)∘f = f(A^Tx+b)), are dense in their ambient class. We construct hitting sets and interpolating sets for these orbits as well as give reconstruction algorithms. Specifically, we obtain the following results:
1) For C_n(ℓ_1(x),…,ℓ_n(x)) ≜ Trace(\begin{pmatrix} ?₁(x) & 1 \\ 1 & 0 \end{pmatrix} ⋅ … ⋅ \begin{pmatrix} ?_n(x) & 1 \\ 1 & 0 \end{pmatrix}), where the ?_is are linearly independent linear functions, we construct a polynomial-sized interpolating set, and give a polynomial-time reconstruction algorithm. By a result of Bringmann, Ikenmeyer and Zuiddam, the set of all such polynomials is dense in VP_e [Karl Bringmann et al., 2018], thus our construction gives the first polynomial-size interpolating set for a dense subclass of VP_e.
2) For polynomials of the form ANF_Δ(?₁(x),…,?_{4^Δ}(x)), where ANF_Δ(x) is the canonical read-once formula in alternating normal form, of depth 2Δ, and the ?_is are linearly independent linear functions, we provide a quasipolynomial-size interpolating set. We also observe that the reconstruction algorithm of [Ankit Gupta et al., 2014] works for all polynomials in this class. This class is also dense in VP_e.
3) Similarly, we give a quasipolynomial-sized hitting set for read-once formulas (not necessarily in alternating normal form) composed with a set of linearly independent linear functions. This gives another dense class in VP_e.
4) We give a quasipolynomial-sized hitting set for polynomials of the form f(?₁(x),…,?_{m}(x)), where f is an m-variate s-sparse polynomial. and the ?_is are linearly independent linear functions in n ≥ m variables. This class is dense in ΣΠΣ.
5) For polynomials of the form ∑_{i=1}^{s}∏_{j=1}^{d}?_{i,j}(x), where the ?_{i,j}s are linearly independent linear functions, we construct a polynomial-sized interpolating set. We also observe that the reconstruction algorithm of [Neeraj Kayal and Chandan Saha, 2019] works for every polynomial in the class. This class is dense in ΣΠΣ. As VP = VNC², 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.
BibTeX - Entry
@InProceedings{medini_et_al:LIPIcs.CCC.2021.19,
author = {Medini, Dori and Shpilka, Amir},
title = {{Hitting Sets and Reconstruction for Dense Orbits in VP\underline\{e\} and \Sigma\Pi\Sigma Circuits}},
booktitle = {36th Computational Complexity Conference (CCC 2021)},
pages = {19:1--19:27},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-193-1},
ISSN = {1868-8969},
year = {2021},
volume = {200},
editor = {Kabanets, Valentine},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14293},
URN = {urn:nbn:de:0030-drops-142930},
doi = {10.4230/LIPIcs.CCC.2021.19},
annote = {Keywords: Algebraic complexity, VP, VNP, algebraic circuits, algebraic formula}
}
|
Keywords: |
|
Algebraic complexity, VP, VNP, algebraic circuits, algebraic formula |
|
Collection: |
|
36th Computational Complexity Conference (CCC 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
08.07.2021 |
