Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR11-083 | 22nd May 2011 04:22

On the power of algebraic branching programs of width two

RSS-Feed




TR11-083
Authors: Eric Allender, Fengming Wang
Publication: 22nd May 2011 04:22
Downloads: 3823
Keywords: 


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.



ISSN 1433-8092 | Imprint