### 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)}.

Original language | English (US) |
---|---|

Title of host publication | STOC '12 - Proceedings of the 2012 ACM Symposium on Theory of Computing |

Pages | 615-623 |

Number of pages | 9 |

DOIs | |

State | Published - Jun 26 2012 |

Event | 44th Annual ACM Symposium on Theory of Computing, STOC '12 - New York, NY, United States Duration: May 19 2012 → May 22 2012 |

### Publication series

Name | Proceedings of the Annual ACM Symposium on Theory of Computing |
---|---|

ISSN (Print) | 0737-8017 |

### Other

Other | 44th Annual ACM Symposium on Theory of Computing, STOC '12 |
---|---|

Country | United States |

City | New York, NY |

Period | 5/19/12 → 5/22/12 |

### All Science Journal Classification (ASJC) codes

- Software

### Keywords

- algebraic branching programs
- arithmetic circuits
- arithmetic formulas
- multilinear computations
- polynomials

## Fingerprint Dive into the research topics of 'Separating multilinear branching programs and formulas'. Together they form a unique fingerprint.

## Cite this

*STOC '12 - Proceedings of the 2012 ACM Symposium on Theory of Computing*(pp. 615-623). (Proceedings of the Annual ACM Symposium on Theory of Computing). https://doi.org/10.1145/2213977.2214034