Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

Paper:

TR16-009 | 28th January 2016 15:54

Identity Testing for constant-width, and commutative, read-once oblivious ABPs

TR16-009
Authors: Rohit Gurjar, Arpita Korwar, Nitin Saxena
Publication: 28th January 2016 17:38
Keywords:

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 variable order. The best hitting-set known for this case had cost \$(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 complexity for the known-order case to \$n^{O(\log w)}\$. In particular, this gives the first polynomial time hitting-set for constant-width ROABP (known-order). However, our hitting-set works only over those fields whose characteristic is zero or large enough. To construct the hitting-set, we use the concept of the rank of partial derivative matrix. Unlike previous approaches whose basic building block is a monomial map, we use a polynomial map.

The second case we consider is that of commutative ROABP. The best known hitting-set for this case had cost
\$d^{O(\log w)}(nw)^{O(\log \log w)}\$, where \$d\$ is the individual degree. We improve this hitting-set complexity to \$(ndw)^{O(\log \log w)}\$. We get this by achieving rank concentration more efficiently.

ISSN 1433-8092 | Imprint