文章基本信息

标题：Deterministic Identity Testing of Read-Once Algebraic Branching Programs
本地全文：下载
作者：Maurice Jansen ; Youming Qiao ; Jayalal Sarma 等
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2010
卷号：2010
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：An algebraic branching program (ABP) is given by a directed acyclic graph with source and sink vertices s and t, respectively, and where edges are labeled by variables or field constants. An ABP computes the sum of weights of all directed paths from s to t, where the weight of a path is taken to be the product of the edge labels on the path. For a read-once ABP every variable appears at most once in the graph. More generally, we consider preprocessed RO-ABPs (PRO-ABP), which are obtained by allowing univariate polynomials on the edges (at most one non-constant polynomial Ti(xi) per variable xi). We study the problem of polynomial identity testing sums of k many PRO-ABPs. We obtain the following results, in case edges are labeled by univariate polynomials of degree at most d, and provided the underlying field has enough elements (more than 2k2d2n5 suffices): 1. Given free access to the PRO-ABPs in the sum, we get a deterministic algorithm that runs in time O(dk2n7s2)+(dn)O(k), where s bounds the size of any largest PRO-ABP given on the input. 2. Given black-box access to the PRO-ABPs computing the individual polynomials in the sum, we get a deterministic algorithm that runs in time k2(dn)O(logn)+(dn)O(k). 3. Given only black-box access to the polynomial computed by the sum of the k PRO-ABPs, we obtain a (dn)O(k+logn) time deterministic algorithm. Items 1. and 3. strengthen two main results of (Shpilka and Volkovich, 2009), who considered polynomial identity testing of sums of k preprocessed read-once formulas.
关键词：Algebraic Branching Programs, derandomization, polynomial identity testing