Gurjar, Rohit ;
Korwar, Arpita ;
Saxena, Nitin ;
Thierauf, Thomas
Deterministic Identity Testing for Sum of Readonce Oblivious Arithmetic Branching Programs
Abstract
A readonce oblivious arithmetic branching program (ROABP) is an arithmetic branching program (ABP) where each variable occurs in at most one layer. We give the first polynomial time whitebox identity test for a polynomial computed by a sum of constantly many ROABPs. We also give a corresponding blackbox algorithm with quasipolynomial time complexity n^(O(log(n))). In both the cases, our time complexity is double exponential in the number of ROABPs.
ROABPs are a generalization of setmultilinear depth3 circuits. The prior results for the sum of constantly many setmultilinear depth3 circuits were only slightly better than bruteforce, i.e. exponentialtime.
Our techniques are a new interplay of three concepts for ROABP: low evaluation dimension, basis isolating weight assignment and lowsupport rank concentration. We relate basis isolation to rank concentration and extend it to a sum of two ROABPs using evaluation dimension (or partial derivatives).
BibTeX  Entry
@InProceedings{gurjar_et_al:LIPIcs:2015:5064,
author = {Rohit Gurjar and Arpita Korwar and Nitin Saxena and Thomas Thierauf},
title = {{Deterministic Identity Testing for Sum of Readonce Oblivious Arithmetic Branching Programs}},
booktitle = {30th Conference on Computational Complexity (CCC 2015)},
pages = {323346},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897811},
ISSN = {18688969},
year = {2015},
volume = {33},
editor = {David Zuckerman},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/5064},
URN = {urn:nbn:de:0030drops50647},
doi = {10.4230/LIPIcs.CCC.2015.323},
annote = {Keywords: PIT, Hittingset, Sum of ROABPs, Evaluation Dimension, Rank Concentration}
}
2015
Keywords: 

PIT, Hittingset, Sum of ROABPs, Evaluation Dimension, Rank Concentration 
Seminar: 

30th Conference on Computational Complexity (CCC 2015)

Issue date: 

2015 
Date of publication: 

2015 