Logo image
On the Power of Algebraic Branching Programs of Width Two
Accepted manuscript   Open access   Peer reviewed

On the Power of Algebraic Branching Programs of Width Two

Eric Allender and Fengming Wang
Computational Complexity, Vol.25(1), pp.217-253
2016
DOI:
https://doi.org/10.7282/T3P270Z6

Abstract

Iterated Matrix Multiplication Arithmetic circuits Algebraic branching programs Matrices Computational complexity
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.
pdf
2.by.2317.55 kBDownloadView
Accepted Manuscript Open Access
url
http://dx.doi.org/10.1007/s00037-015-0114-7View
Computational Complexity
url
Report an accessibility issueView
Please complete a content remediation request to report an accessibility issue with a library electronic resource, website, or service.

Metrics

323 File downloads
115 Record Views

Details

Logo image