Deterministic Identity Testing for Sum of Read-Once Oblivious Arithmetic Branching Programs
2017
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({\rm log}\,n)}}\). In both the cases, our time complexity is double exponential in the number of ROABPs.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
37
References
23
Citations
NaN
KQI