Gurjar, Rohit ;
Korwar, Arpita ;
Saxena, Nitin
Identity Testing for ConstantWidth, and Commutative, ReadOnce Oblivious ABPs
Abstract
We give improved hittingsets for two special cases of Readonce Oblivious Arithmetic Branching Programs (ROABP). First is the case of an ROABP with known variable order. The best hittingset 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 constantwidth ROABP, nothing better than a quasipolynomial bound was known. We improve the hittingset complexity for the knownorder case to n^{O(log(w))}. In particular, this gives the first polynomial time hittingset for constantwidth ROABP (knownorder). However, our hittingset works only over those fields whose characteristic is zero or large enough. To construct the hittingset, 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 hittingset for this case had cost d^{O(log(w))}(nw)^{O(log(log(w)))}, where d is the individual degree. We improve this hittingset complexity to (ndw)^{O(log(log(w)))}. We get this by achieving rank concentration more efficiently.
BibTeX  Entry
@InProceedings{gurjar_et_al:LIPIcs:2016:5843,
author = {Rohit Gurjar and Arpita Korwar and Nitin Saxena},
title = {{Identity Testing for ConstantWidth, and Commutative, ReadOnce Oblivious ABPs}},
booktitle = {31st Conference on Computational Complexity (CCC 2016)},
pages = {29:129:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770088},
ISSN = {18688969},
year = {2016},
volume = {50},
editor = {Ran Raz},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/5843},
URN = {urn:nbn:de:0030drops58438},
doi = {10.4230/LIPIcs.CCC.2016.29},
annote = {Keywords: PIT, hittingset, constantwidth ROABPs, commutative ROABPs}
}
19.05.2016
Keywords: 

PIT, hittingset, constantwidth ROABPs, commutative ROABPs 
Seminar: 

31st Conference on Computational Complexity (CCC 2016)

Issue date: 

2016 
Date of publication: 

19.05.2016 