Theory of Computing
-------------------
Title : Identity Testing for Constant-Width, and Any-Order, Read-Once Oblivious Arithmetic Branching Programs
Authors : Rohit Gurjar, Arpita Korwar, and Nitin Saxena
Volume : 13
Number : 2
Pages : 1-21
URL : https://theoryofcomputing.org/articles/v013a002
Abstract
--------
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(\log n)}$ where $n$ is the
number of variables and $w$ 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
$n^{O(\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-$w$ ROABPs in any order of the variables. The best known
hitting-set for this case had size $d^{O(\log w)}(nw)^{O(\log \log w)}$,
where $d$ is the individual degree. We improve the hitting-set size to
$(ndw)^{O(\log \log w)}$.
A conference version of this paper appeared in the Proceedings of the
31st Computational Complexity Conference, 2016 (CCC'16).