文章基本信息

标题：Identity Testing for Constant-Width, and Any-Order, Read-Once Oblivious Arithmetic Branching Programs
本地全文：下载
作者：Rohit Gurjar ; Arpita Korwar ; Nitin Saxena 等
期刊名称：Theory of Computing
印刷版ISSN：1557-2862
电子版ISSN：1557-2862
出版年度：2017
卷号：13
出版社：University of Chicago
摘要：We give improved hitting-sets for two special cases of Read-once Oblivious Arithmetic Branching Programs (ROABP). First is the case of an ROABP with known order of the variables. The best previously known hitting-set for this case had size (nw)O(logn)(nw)O(log⁡n) where nn is the number of variables and ww is the width of the ROABP. Even for a constant-width ROABP, nothing better than a quasi-polynomial bound was known. We improve the hitting-set size for the known-order case to nO(logw)nO(log⁡w). In particular, this gives the first polynomial-size hitting-set for constant-width ROABP (known-order). However, our hitting-set only works when the characteristic of the field is zero or large enough. To construct the hitting-set, we use the concept of the rank of the partial derivative matrix. Unlike previous approaches which build up from mapping variables to monomials, we map variables to polynomials directly.The second case we consider is that of polynomials computable by width-ww ROABPs in any order of the variables. The best known hitting-set for this case had size dO(logw)(nw)O(loglogw)dO(log⁡w)(nw)O(log⁡log⁡w), where dd is the individual degree. We improve the hitting-set size to (ndw)O(loglogw)(ndw)O(log⁡log⁡w).
关键词：polynomial identity testing; hitting sets; arithmetic branching programs