On Algebraic Branching Programs of Small Width

DOI10.1145/3209663zbMath1426.68089arXiv1702.05328OpenAlexW2590079450MaRDI QIDQ4625653

Jeroen Zuiddam, Karl Bringmann, Christian Ikenmeyer

Publication date: 25 February 2019

Published in: Journal of the ACM (Search for Journal in Brave)

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

zbMATH Keywords

algebraic branching programsiterated matrix multiplicationalgebraic complexity theoryformula sizeborder complexity

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Other nonclassical models of computation (68Q09)

Related Items (6)

A note on VNP-completeness and border complexity ⋮ Discovering the Roots: Uniform Closure Results for Algebraic Classes Under Factoring ⋮ On the closures of monotone algebraic classes and variants of the determinant ⋮ Unnamed Item ⋮ Blackbox identity testing for sum of special ROABPs and its border class ⋮ Unnamed Item

This page was built for publication: On Algebraic Branching Programs of Small Width