Name
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 nO(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 starting point is a monomial map, we use a polynomial map directly. The second case we consider is that of commutative ROABP. The best known hitting-set for this case had cost dO(log w)(nw)O(log log w), where d is the individual degree. We improve this hitting-set complexity to (ndw)O(log logw). We get this by achieving rank concentration more efficiently. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.4230/LIPIcs.CCC.2016.29 | Electronic Colloquium on Computational Complexity |
Keywords | DocType | Volume |
PIT,hitting-set,constant-width ROABPs,commutative ROABPs | Journal | abs/1601.08031 |
ISSN | Citations | PageRank |
1868-8969 | 4 | 0.44 |
References | Authors | |
15 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Rohit Gurjar | 1 | 17 | 1.04 |
| Arpita Korwar | 2 | 29 | 3.60 |
| Nitin Saxena | 3 | 280 | 26.72 |