Separation Between Read-once Oblivious Algebraic Branching Programs (ROABPs) and Multilinear Depth-three Circuits
Separation Between Read-once Oblivious Algebraic Branching Programs (ROABPs) and Multilinear Depth-three Circuits
复制标题
一次性读取的不经意代数分支程序 (ROABP) 与多线性深度三电路之间的分离
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Chandan Saha
中科院分区：
文献类型：
--
作者：
N. Kayal;Vineet Nair;Chandan Saha
我们证明了两种研究得很好的代数计算模型，即一次可读的不经意的代数分支程序(ROABPs)和多线性深度3电路之间的指数分离。具体地说，我们证明了：(1)存在一个显式n元多项式，它可以由线性大小的多线性深度-3电路(只有两个乘积门)计算，使得它的每一次ROABP计算需要2个Ω(N)大小。(2)任何计算imm~n，d(d，n×n个符号矩阵的迭代矩阵乘法多项式)的多线性深度三回路都有n个Ω(D)长。通过聚(n，d)大小的ROABP可以容易地计算IMMn，d。(3)此外，(2)的证明给出了多线性深度四电路和多线性深度三电路之间的指数分离：存在一个显式的n元d次多项式，可由多(N)大小的多线性深度四电路计算，使得计算它的任何多线性深度三电路的长度为nΩ(D)。这改进了这两个模型之间参考文献[36]的准多项式分离。(1)中的硬多项式是利用扩展图与评价维度量[15，33，34，36]相结合的新应用来构造的，而(2)中的硬多项式是通过对文献[32]中的偏导数度量的一种新的适应来证明的。我们的下限适用于任何领域。
We show an exponential separation between two well-studied models of algebraic computation, namely, read-once oblivious algebraic branching programs (ROABPs) and multilinear depth-three circuits. In particular, we show the following: (1) There exists an explicit n-variate polynomial computable by linear sized multilinear depth-three circuits (with only two product gates) such that every ROABP computing it requires 2Ω(n) size. (2) Any multilinear depth-three circuit computing IMMn,d (the iterated matrix multiplication polynomial formed by multiplying d, n × n symbolic matrices) has nΩ(d) size. IMMn,d can be easily computed by a poly(n,d) sized ROABP. (3) Further, the proof of (2) yields an exponential separation between multilinear depth-four and multilinear depth-three circuits: There is an explicit n-variate, degree d polynomial computable by a poly(n) sized multilinear depth-four circuit such that any multilinear depth-three circuit computing it has size nΩ(d). This improves upon the quasi-polynomial separation of Reference [36] between these two models. The hard polynomial in (1) is constructed using a novel application of expander graphs in conjunction with the evaluation dimension measure [15, 33, 34, 36], while (2) is proved via a new adaptation of the dimension of the partial derivatives measure of Reference [32]. Our lower bounds hold over any field.
一次读取的不经意算术分支程序之和的确定性身份测试
影响因子：
1.4
作者：
Rohit Gurjar;Arpita Korwar;Nitin Saxena;Thomas Thierauf
通讯作者：
Thomas Thierauf
影响因子：
0.5
作者：
S. Jukna
通讯作者：
S. Jukna