On the power of algebraic branching programs of width two

Eric Allender; Fengming Wang

doi:10.1007/s00037-015-0114-7

On the power of algebraic branching programs of width two

Eric Allender, Fengming Wang

School of Arts and Sciences, Computer Science

Research output: Contribution to journal › Article › peer-review

17 Scopus citations

Abstract

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.

Original language	English (US)
Pages (from-to)	217-253
Number of pages	37
Journal	Computational Complexity
Volume	25
Issue number	1
DOIs	https://doi.org/10.1007/s00037-015-0114-7
State	Published - Mar 1 2016

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Mathematics
Computational Theory and Mathematics
Computational Mathematics

Keywords

Iterated matrix multiplication
algebraic branching programs
arithmetic circuits

Access to Document

10.1007/s00037-015-0114-7

Cite this

@article{6cf425a847a6424e9d72441cf1af1df6,

title = "On the power of algebraic branching programs of width two",

abstract = "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.",

keywords = "Iterated matrix multiplication, algebraic branching programs, arithmetic circuits",

author = "Eric Allender and Fengming Wang",

note = "Publisher Copyright: {\textcopyright} 2015, Springer Basel.",

year = "2016",

month = mar,

day = "1",

doi = "10.1007/s00037-015-0114-7",

language = "English (US)",

volume = "25",

pages = "217--253",

journal = "Computational Complexity",

issn = "1016-3328",

publisher = "Birkhauser Verlag Basel",

number = "1",

}

TY - JOUR

T1 - On the power of algebraic branching programs of width two

AU - Allender, Eric

AU - Wang, Fengming

PY - 2016/3/1

Y1 - 2016/3/1

N2 - 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.

AB - 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.

KW - Iterated matrix multiplication

KW - algebraic branching programs

KW - arithmetic circuits

UR - http://www.scopus.com/inward/record.url?scp=84958149254&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84958149254&partnerID=8YFLogxK

U2 - 10.1007/s00037-015-0114-7

DO - 10.1007/s00037-015-0114-7

M3 - Article

AN - SCOPUS:84958149254

SN - 1016-3328

VL - 25

SP - 217

EP - 253

JO - Computational Complexity

JF - Computational Complexity

IS - 1

ER -

On the power of algebraic branching programs of width two

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this