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

DOI10.4230/LIPICS.CCC.2016.30zbMATH Open1380.68175arXiv1511.07136OpenAlexW2277564371MaRDI QIDQ5368764FDOQ5368764

Authors:

Publication date: 10 October 2017

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.

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

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

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)

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
• Title not available (Why is that?)
• 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
• Identity testing and lower bounds for read-\(k\) oblivious algebraic branching programs
• Separation between read-once oblivious algebraic branching programs (ROABPs) and multilinear depth three circuits
• Title not available (Why is that?)
• 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)