Deterministic Identity Testing for Sum of Read Once ABPs
Rohit Gurjar, Arpita Korwar, Nitin Saxena, Thomas Thierauf · arXiv (Cornell University) · 2014
A read once ABP is an arithmetic branching program with each variable occurring 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 quasi-polynomial time complexity, i.e. n. The motivating special case of this model is sum of constantly many set-multilinear depth-3 circuits. The prior results for that model were only slightly better than bruteforce (i.e. exponential-time). Our techniques are a new interplay of three concepts for ROABP: low evaluation dimension, basis isolating weight assignment and low-support rank concentration.