ECCC-Report TR11-083https://eccc.weizmann.ac.il/report/2011/083Comments and Revisions published for TR11-083en-usSun, 22 May 2011 04:22:57 +0300
Paper TR11-083
| On the power of algebraic branching programs of width two |
Eric Allender,
Fengming Wang
https://eccc.weizmann.ac.il/report/2011/083We 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.
Sun, 22 May 2011 04:22:57 +0300https://eccc.weizmann.ac.il/report/2011/083