Deterministic Identity Testing for Sum of Read Once ABPs
Deterministic Identity Testing for Sum of Read Once ABPs
复制标题
读取一次 ABP 总和的确定性身份测试
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
T. Thierauf
中科院分区：
文献类型：
--
作者：
R. Gurjar;A. Korwar;Nitin Saxena;T. Thierauf
读一次ABP是一个算术分支程序，每个变量最多出现在一层。我们给出了第一个多项式时间白盒身份测试的多项式计算的总和不断许多ROABP。给出了相应的黑盒算法，其时间复杂度为n.该模型的激励特例是许多集多线性深度3电路的总和。该模型的先前结果仅略好于蛮力（即指数时间）。我们的技术是一个新的相互作用的三个概念的ROABP：低评价维度，基础隔离权重分配和低支持等级浓度。
A read once ABP is an arithmetic branching program with each variable occurring 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, i.e. n. The motivating special case of this model is sum of constantly many set-multilinear depth-3 circuits. The prior results for that model were only slightly better than bruteforce (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.