Identity testing and lower bounds for read-k oblivious algebraic branching programs

DOI10.4230/LIPICS.CCC.2016.30MaRDI QIDQ5368764zbMATH OpenOpenAlexFDO

Authors

Publication date 10 October 2017

Full work available at URL https://arxiv.org/abs/1511.07136

zbMATH Keywords

lower boundsderandomizationalgebraic complexitypolynomial identity testing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Data structures (68P05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: Read-$k$ oblivious algebraic branching programs are a natural generalization of the well-studied model of read-once oblivious algebraic branching program (ROABPs). In this work, we give an exponential lower bound of $exp(n/k^{O(k)})$ on the width of any read-$k$ oblivious ABP computing some explicit multilinear polynomial $f$ that is computed by a polynomial size depth-$3$ circuit. We also study the polynomial identity testing (PIT) problem for this model and obtain a white-box subexponential-time PIT algorithm. The algorithm runs in time $2^{ildeO(n^{1-1/2^{k-1}})}$ and needs white box access only to know the order in which the variables appear in the ABP.

Recommendations

• Identity testing and lower bounds for read-\(k\) oblivious algebraic branching programs
• Deterministic identity testing for sum of read-once oblivious arithmetic branching programs
• Deterministic identity testing for sum of read-once oblivious arithmetic branching programs
• Deterministic black-box identity testing \(\pi\)-ordered algebraic branching programs
• Hitting sets for multilinear read-once algebraic branching programs, in any order

Cited in

(9)

• Separation between read-once oblivious algebraic branching programs (ROABPs) and multilinear depth-three circuits
• Deterministic black-box identity testing \(\pi\)-ordered algebraic branching programs
• 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
• Deterministic identity testing for sum of read-once oblivious arithmetic branching programs
• Separation between read-once oblivious algebraic branching programs (ROABPs) and multilinear depth three circuits
• Identity testing and lower bounds for read-\(k\) oblivious algebraic branching programs
• scientific article; zbMATH DE number 7561749 (Why is no real title available?)
• A quadratic lower bound for homogeneous algebraic branching programs

This page was built for publication: Identity testing and lower bounds for read-\(k\) oblivious algebraic branching programs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5368764)