2026-07-22T09:02:47Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5064 2024-03-06T10:35:47Z ddc:004 open_access

Deterministic Identity Testing for Sum of Read-once Oblivious Arithmetic Branching Programs Gurjar, Rohit Korwar, Arpita Saxena, Nitin Thierauf, Thomas PIT Hitting-set Sum of ROABPs Evaluation Dimension Rank Concentration 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). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Rohit Gurjar and Arpita Korwar and Nitin Saxena and Thomas Thierauf 2015 Is Part Of LIPIcs, Volume 33, 30th Conference on Computational Complexity (CCC 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2015.323 urn:nbn:de:0030-drops-50647 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2015.323 eng https://creativecommons.org/licenses/by/3.0/legalcode