Name
Abstract | ||
|---|---|---|
This work deals with the power of linear algebra in the context of multilinear computation. By linear algebra we mean algebraic branching programs (ABPs) which are known to be computationally equivalent to two basic tools in linear algebra: iterated matrix multiplication and the determinant. We compare the computational power of multilinear ABPs to that of multilinear arithmetic formulas, and prove a tight super-polynomial separation between the two models. Specifically, we describe an explicit n-variate polynomial F that is computed by a linear-size multilinear ABP but every multilinear formula computing F must be of size nΩ(log n). |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1145/2213977.2214034 | STOC '12 Proceedings of the forty-fourth annual ACM symposium on Theory of computing |
Keywords | DocType | Citations |
size n,multilinear abps,separating multilinear,multilinear arithmetic formula,log n,linear algebra,linear-size multilinear,computational power,explicit n-variate polynomial f,multilinear formula computing f,multilinear computation,matrix multiplication,branching program,polynomials,model specification | Journal | 9 |
PageRank | References | Authors |
0.56 | 11 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Zeev Dvir | 1 | 437 | 30.85 |
| Guillaume Malod | 2 | 54 | 4.53 |
| Sylvain Perifel | 3 | 64 | 6.61 |
| Amir Yehudayoff | 4 | 530 | 43.83 |