文章基本信息

标题：Deterministic Black-Box Identity Testing -Ordered 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
摘要：In this paper we study algebraic branching programs (ABPs) with restrictions on the order and the number of reads of variables in the program. Given a permutation of n variables, for a -ordered ABP (-OABP), for any directed path p from source to sink, a variable can appear at most once on p, and the order in which variables appear on p must respect . An ABP A is said to be of read r, if any variable appears at most r times in A. Our main result pertains to the identity testing problem. Over any field F and in the black-box model, i.e. given only query access to the polynomial, we have the following result: read r -OABP computable polynomials can be tested in \DTIME[2O(rlogrlog2nloglogn)]. Our next set of results investigates the computational limitations of OABPs. It is shown that any OABP computing the determinant or permanent requires size (2nn) and read (2nn2) . We give a multilinear polynomial p in 2n+1 variables over some specifically selected field G, such that any OABP computing p must read some variable at least 2n times. We show that the elementary symmetric polynomial of degree r in n variables can be computed by a size O(rn) read r OABP, but not by a read (r−1) OABP, for any 02r−1n. Finally, we give an example of a polynomial p and two variables orders = , such that p can be computed by a read-once -OABP, but where any -OABP computing p must read some variable at least 2n
关键词：Algebraic Branching Programs, derandomization, polynomial identity testing