Deterministic Identity Testing for Sum of Read-Once Oblivious Arithmetic Branching Programs
Deterministic Identity Testing for Sum of Read-Once Oblivious Arithmetic Branching Programs
复制标题
一次读取的不经意算术分支程序之和的确定性身份测试
DOI：
10.1007/s00037-016-0141-z
复制
发表时间：
2017
影响因子：
1.4
通讯作者：
Thomas Thierauf
中科院分区：
文献类型：
--
作者：
Rohit Gurjar;Arpita Korwar;Nitin Saxena;Thomas Thierauf
一次读不经意算术分支程序（ROABP）是一个算术分支程序（ABP），其中每个变量最多出现在一个层中。我们给出了第一个多项式时间白盒身份测试的多项式计算的总和不断许多ROABP。我们也给出了相应的黑盒算法的拟多项式时间复杂度。在这两种情况下，我们的时间复杂度是ROABP数量的双指数。ROABP是集合多线性深度3电路的推广。之前的结果是，许多集-多线性深度3电路的总和只比蛮力稍好，即，指数时间我们的技术是一个新的相互作用的三个概念的ROABP：低评价维度，基础隔离权重分配和低支持等级浓度。我们将基隔离与秩集中联系起来，并利用评价维将其扩展到两个ROABPs之和。
Aread-once oblivious arithmetic branching program (ROABP)is an arithmetic branching program (ABP) where each variable occurs in at most one layer. We give the first polynomial-time whitebox identity test for a polynomial computed by a sum of constantly many ROABPs. We also give a corresponding blackbox algorithm with quasi-polynomial-time complexity. In both the cases, our time complexity is double exponential in the number of ROABPs.ROABPs are a generalization of set-multilinear depth-3 circuits. The prior results for the sum of constantly many set-multilinear depth-3 circuits were only slightly better than brute force, i.e., exponential time. Our techniques are a new interplay of three concepts for ROABP: low evaluation dimension, basis isolating weight assignment and low-support rank concentration. We relate basis isolation to rank concentration and extend it to a sum of two ROABPs using evaluation dimension.
登录
查看更多内容
有界深度多线性公式的次指数大小命中集
影响因子：
1.4
作者：
R. Oliveira;Amir Shpilka;Ben lee Volk
通讯作者：
Ben lee Volk
深度 3 电路的黑盒多项式恒等测试
DOI：
10.1109/focs.2009.67
发表时间：
2009
期刊：
2009 50th Annual IEEE Symposium on Foundations of Computer Science
影响因子：
--
作者：
N. Kayal;Shubhangi Saraf
通讯作者：
Shubhangi Saraf
一次性读取的不经意代数分支程序 (ROABP) 与多线性深度三电路之间的分离
DOI：
--
发表时间：
2020
期刊：
Symposium on Theoretical Aspects of Computer Science
影响因子：
--
作者：
N. Kayal;Vineet Nair;Chandan Saha
通讯作者：
Chandan Saha
Mod-2-OBDD - 一种概括 EXOR 乘积和和有序二元决策图的数据结构
DOI：
--
发表时间：
1996
期刊：
Formal Methods Syst. Des.
影响因子：
--
作者：
Jordan Gergov;C. Meinel
通讯作者：
C. Meinel
DOI：
--
发表时间：
1991
期刊：
Symposium on the Theory of Computing
影响因子：
--
作者：
N. Nisan
通讯作者：
N. Nisan