Identity Testing and Lower Bounds for Read- k Oblivious Algebraic Branching Programs

DOI10.1145/3170709zbMath1427.68077OpenAlexW2783226595MaRDI QIDQ4973871

No author found.

Publication date: 6 December 2019

Published in: ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3170709

zbMATH Keywords

lower boundsalgebraic complexity theorypolynomial identity testingalgebraic circuits

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Networks and circuits as models of computation; circuit complexity (68Q06)

Related Items (4)

Unnamed Item ⋮ Unnamed Item ⋮ Lower bounds for special cases of syntactic multilinear ABPs ⋮ A super-quadratic lower bound for depth four arithmetic circuits

This page was built for publication: Identity Testing and Lower Bounds for Read- k Oblivious Algebraic Branching Programs