文章基本信息

标题：Improved Explicit Hitting-Sets for ROABPs
本地全文：下载
作者：Zeyu Guo ; Rohit Gurjar
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：176
页码：4:1-4:16
DOI：10.4230/LIPIcs.APPROX/RANDOM.2020.4
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We give improved explicit constructions of hitting-sets for read-once oblivious algebraic branching programs (ROABPs) and related models. For ROABPs in an unknown variable order, our hitting-set has size polynomial in (nr)^{(log n)/(max{1, log log n-log log r})}d over a field whose characteristic is zero or large enough, where n is the number of variables, d is the individual degree, and r is the width of the ROABP. A similar improved construction works over fields of arbitrary characteristic with a weaker size bound. Based on a result of Bisht and Saxena (2020), we also give an improved explicit construction of hitting-sets for sum of several ROABPs. In particular, when the characteristic of the field is zero or large enough, we give polynomial-size explicit hitting-sets for sum of constantly many log-variate ROABPs of width r = 2^{O(log d/log log d)}. Finally, we give improved explicit hitting-sets for polynomials computable by width-r ROABPs in any variable order, also known as any-order ROABPs. Our hitting-set has polynomial size for width r up to 2^{O(log(nd)/log log(nd))} or 2^{O(log^{1-Îµ} (nd))}, depending on the characteristic of the field. Previously, explicit hitting-sets of polynomial size are unknown for r = Ï(1).
关键词：polynomial identity testing; hitting-set; ROABP; arithmetic branching programs; derandomization