Deterministic identity testing for sum of read-once oblivious arithmetic branching programs
From MaRDI portal
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 . In both the cases, our time complexity is double exponential in the number of ROABPs. ROABPs are a generalization of set-multilinear depth- circuits. The prior results for the sum of constantly many set-multilinear depth- 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).
Recommendations
- Deterministic identity testing for sum of read-once oblivious arithmetic branching programs
- Identity Testing for Constant-Width, and Any-Order, Read-Once Oblivious Arithmetic Branching Programs
- Identity testing and lower bounds for read-\(k\) oblivious algebraic branching programs
- Identity testing and lower bounds for read-\(k\) oblivious algebraic branching programs
- Identity testing, multilinearity testing, and monomials in read-once/twice formulas and branching programs
- Identity testing for constant-width, and commutative, read-once oblivious ABPs
- A deterministic algorithm for testing the equivalence of read-once branching programs with small discrepancy
- Deterministic black-box identity testing -ordered algebraic branching programs
- Complete derandomization of identity testing and reconstruction of read-once formulas
- scientific article; zbMATH DE number 7204283
Cites work
- A probabilistic remark on algebraic program testing
- An almost optimal rank bound for depth-3 identities
- Arithmetic circuits: a chasm at depth 3
- Arithmetic circuits: a survey of recent results and open questions
- Black box polynomial identity testing of generalized depth-3 arithmetic circuits with bounded top fan-in
- Blackbox identity testing for bounded top-fanin depth-3 circuits: the field doesn't matter
- Blackbox Polynomial Identity Testing for Depth 3 Circuits
- Derandomizing polynomial identity tests means proving circuit lower bounds
- Deterministic black-box identity testing -ordered algebraic branching programs
- Deterministic identity testing for sum of read-once oblivious arithmetic branching programs
- Deterministic polynomial identity testing in non-commutative models
- Efficient algorithms for the transformation between different types of binary decision diagrams
- Fast Probabilistic Algorithms for Verification of Polynomial Identities
- FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
- Hitting sets for multilinear read-once algebraic branching programs, in any order
- Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits
- scientific article; zbMATH DE number 3651744 (Why is no real title available?)
- scientific article; zbMATH DE number 6829282 (Why is no real title available?)
- Locally Decodable Codes with Two Queries and Polynomial Identity Testing for Depth 3 Circuits
- Lower bounds and separations for constant depth multilinear circuits
- On identity testing of tensors, low-rank recovery and compressed sensing
- Polynomial identity testing for depth 3 circuits
- Progress on polynomial identity testing
- Progress on polynomial identity testing. II
- Quasi-polynomial hitting-set for set-depth-\({\Delta}\) formulas
- Randomness efficient identity testing of multivariate polynomials
- Separation between read-once oblivious algebraic branching programs (ROABPs) and multilinear depth three circuits
Cited in
(17)- Blackbox identity testing for sum of special ROABPs and its border class
- Lower bounds for arithmetic circuits via the Hankel matrix
- Lower bounds and PIT for non-commutative arithmetic circuits with restricted parse trees
- Deterministic black-box identity testing -ordered algebraic branching programs
- Deterministic identity testing for sum of read-once oblivious arithmetic branching programs
- scientific article; zbMATH DE number 7009617 (Why is no real title available?)
- Identity testing and lower bounds for read-\(k\) oblivious algebraic branching programs
- scientific article; zbMATH DE number 7471587 (Why is no real title available?)
- scientific article; zbMATH DE number 7204283 (Why is no real title available?)
- Identity testing for constant-width, and commutative, read-once oblivious ABPs
- Identity testing and lower bounds for read-\(k\) oblivious algebraic branching programs
- Identity Testing for Constant-Width, and Any-Order, Read-Once Oblivious Arithmetic Branching Programs
- Improved Explicit Hitting-Sets for ROABPs
- scientific article; zbMATH DE number 7758310 (Why is no real title available?)
- Lower bounds for set-multilinear branching programs
- Derandomizing multivariate polynomial factoring for low degree factors
- Hitting sets for orbits of circuit classes and polynomial families
This page was built for publication: Deterministic identity testing for sum of read-once oblivious arithmetic branching programs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1686835)
