2026-08-17T16:25:11Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5843 2024-03-06T10:37:12Z ddc:004 open_access

Identity Testing for Constant-Width, and Commutative, Read-Once Oblivious ABPs Gurjar, Rohit Korwar, Arpita Saxena, Nitin PIT hitting-set constant-width ROABPs commutative ROABPs 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 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 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Rohit Gurjar and Arpita Korwar and Nitin Saxena 2016 Is Part Of LIPIcs, Volume 50, 31st Conference on Computational Complexity (CCC 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2016.29 urn:nbn:de:0030-drops-58438 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2016.29 eng https://creativecommons.org/licenses/by/3.0/legalcode