Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR14-158 | 29th May 2015 15:42

Deterministic Identity Testing for Sum of Read-Once Oblivious Arithmetic Branching Programs

RSS-Feed

Abstract:

A read-once 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 quasi-polynomial 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 set-multilinear depth-$3$ circuits. The prior results for the sum of constantly many set-multilinear depth-$3$ circuits were only slightly better than brute-force, 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. We relate basis isolation to rank concentration and extend it to a sum of two ROABPs using evaluation dimension (or partial derivatives).



Changes to previous version:

Revision 1 was an outdated file. Some changes in the presentation and incorporating the reviewers' comments. There are no new theorems.


Revision #1 to TR14-158 | 16th May 2015 13:11

Deterministic Identity Testing for Sum of Read-Once Oblivious Arithmetic Branching Programs


Abstract:

A read-once 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 quasi-polynomial 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 set-multilinear depth-$3$ circuits. The prior results for the sum of constantly many set-multilinear depth-$3$ circuits were only slightly better than brute-force, 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. We relate basis isolation to rank concentration and extend it to a sum of two ROABPs using evaluation dimension (or partial derivatives).



Changes to previous version:

Some changes in the presentation and incorporating the reviewers' comments. There are no new theorems.


Paper:

TR14-158 | 26th November 2014 20:00

Deterministic Identity Testing for Sum of Read Once ABPs





TR14-158
Authors: Rohit Gurjar, Arpita Korwar, Nitin Saxena, Thomas Thierauf
Publication: 27th November 2014 09:32
Downloads: 1194
Keywords: 


Abstract:

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^{O(\log 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 brute-force (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.



ISSN 1433-8092 | Imprint