Sign in
Back
On the Power of Algebraic Branching Programs of Width Two
Book chapter   Peer reviewed

On the Power of Algebraic Branching Programs of Width Two

Eric Allender and Fengming Wang
Automata, Languages and Programming, pp.736-747
Lecture Notes in Computer Science, Springer Berlin Heidelberg
2011
DOI: https://doi.org/10.1007/978-3-642-22006-7_62

Abstract

Algebraic Complexity Irreducible Polynomial Degree Sequence Boolean Circuit Arithmetic Formula
We show that there are families of polynomials having small depth-two arithmetic circuits that cannot be expressed by algebraic branching programs of width two. This clarifies the complexity of the problem of computing the product of a sequence of two-by-two matrices, which arises in several settings.

Metrics

7 Record Views

Details