Hitting sets and reconstruction for dense orbits in VPe and ΣΠΣ circuits
Hitting sets and reconstruction for dense orbits in VPe and ΣΠΣ circuits
复制标题
VPe 和 ΣΠΣ 电路中密集轨道的命中集和重构
DOI：
10.4230/lipics.ccc.2021.19
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Amir Shpilka
中科院分区：
文献类型：
--
作者：
D. Medini;Amir Shpilka
本文研究了VPe（多项式大小的公式）中的多项式和VIPe（多项式大小的深度为3的回路）中的多项式，它们的轨道在仿射群GLAffn（F）的作用下（（A，B）∈ GLAffn（F）对多项式f ∈ F [x]的作用定义为（A，B）o f = f（AT x + B）），在它们的环境类中是稠密的.我们构造了这些轨道的碰集和内插集，并给出了重构算法。具体来说，我们得到了以下结果：1.对于[EQUATION]，其中插值函数是线性无关的线性函数，我们构造了一个多项式大小的插值集，并给出了一个多项式时间重构算法。根据Bringmann，Ikenmeyer和Zuiddam的一个结果，所有这样的多项式的集合在VPe [14]中是稠密的，因此我们构造了VPe的一个稠密子类的第一个多项式大小的插值集. 2.对于形式为ANF Δ（λ 1（x），.，其中ANF Δ（x）是深度为2 Δ的交替范式的标准只读公式，并且Δ是线性无关的线性函数，我们提供了一个拟多项式大小的插值集。我们还观察到[35]的重建算法适用于该类中的所有多项式。这个类在VPe中也很密集。3.同样，我们给出了一个准多项式大小的命中集只读一次公式（不一定在交替范式）组成的一组线性无关的线性函数。这给出了Vpe中的另一个稠密类。4.我们给出了形式为f（x~1（x），...，...的多项式的一个拟多项式大小的碰集，其中f是m变量s稀疏多项式。并且这些函数是n ≥ m个变量的线性无关的线性函数。这个班的学生很多。5.对于形式为<$si = 1 <$dj = 1 <$i，j（x）的多项式，其中<$i，js是线性无关的线性函数，我们构造了一个多项式大小的插值集.我们还观察到[45]的重建算法适用于该类中的每个多项式。这个班的学生很多。当VP = VNC2时，我们对VPe的结果立即转化为VP，其中参数具有拟多项式爆破。如果我们的任何一个碰集或插值集都是鲁棒的，那么这将立即产生一个超类的碰集，其中相关的类是稠密的，因此也是超类的下界。不幸的是，我们还证明了，我们发现的那种结构（这是定义在k-独立多项式映射）不一定会产生强大的命中集。
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 GLaffn (F) (the action of (A, b) ∈ GLaffn (F) on a polynomial f ∈ F[x] is defined as (A, b) ο f = f (AT x + 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 [EQUATION], 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 VPe [14], thus our construction gives the first polynomial-size interpolating set for a dense subclass of VPe. 2. For polynomials of the form ANFΔ (ℓ1(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 [35] works for all polynomials in this class. This class is also dense in VPe. 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 VPe. 4. We give a quasipolynomial-sized hitting set for polynomials of the form f(ℓ1(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 Σsi=1 Πdj=1 ℓi,j (x), where the ℓi,js are linearly independent linear functions, we construct a polynomial-sized interpolating set. We also observe that the reconstruction algorithm of [45] works for every polynomial in the class. This class is dense in ΣΠΣ. 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.
影响因子：
22.7
作者：
Stephen A. Fenner;Rohit Gurjar;Thomas Thierauf
通讯作者：
Thomas Thierauf
从代数电路复杂性证明复杂性下界
影响因子：
1
作者：
Forbes, Michael A.;Shpilka, Amir;Tzameret, Iddo;Wigderson, Avi
通讯作者：
Wigderson, Avi