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 \(\pi\)-ordered algebraic branching programs
- Complete derandomization of identity testing and reconstruction of read-once formulas
- scientific article; zbMATH DE number 7204283
Cites work
- scientific article; zbMATH DE number 3651744 (Why is no real title available?)
- scientific article; zbMATH DE number 6829282 (Why is no real title available?)
- 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 Polynomial Identity Testing for Depth 3 Circuits
- Blackbox identity testing for bounded top-fanin depth-3 circuits: the field doesn't matter
- Derandomizing polynomial identity tests means proving circuit lower bounds
- Deterministic black-box identity testing \(\pi\)-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
- FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
- Fast Probabilistic Algorithms for Verification of Polynomial Identities
- Hitting sets for multilinear read-once algebraic branching programs, in any order
- Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits
- 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
(14)- Deterministic black-box identity testing \(\pi\)-ordered algebraic branching programs
- Improved Explicit Hitting-Sets for ROABPs
- scientific article; zbMATH DE number 7758310 (Why is no real title available?)
- Identity Testing for Constant-Width, and Any-Order, Read-Once Oblivious Arithmetic Branching Programs
- Lower bounds and PIT for non-commutative arithmetic circuits with restricted parse trees
- Blackbox identity testing for sum of special ROABPs and its border class
- scientific article; zbMATH DE number 7204283 (Why is no real title available?)
- Lower bounds for arithmetic circuits via the Hankel matrix
- Deterministic identity testing for sum of read-once oblivious arithmetic branching programs
- Identity testing and lower bounds for read-\(k\) oblivious algebraic branching programs
- Identity testing for constant-width, and commutative, read-once oblivious ABPs
- Identity testing and lower bounds for read-\(k\) oblivious algebraic branching programs
- scientific article; zbMATH DE number 7009617 (Why is no real title available?)
- scientific article; zbMATH DE number 7471587 (Why is no real title available?)
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)
