Skip to main content

Separating multilinear branching programs and formulas

Author(s): Dvir, Zeev; Malod, G; Perifel, S; Yehudayoff, A

To refer to this page use:
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).
Publication Date: 9-May-2012
Electronic Publication Date: 2012
Citation: Dvir, Z, Malod, G, Perifel, S, Yehudayoff, A. (2012). Separating multilinear branching programs and formulas. 615 - 623. doi:10.1145/2213977.2214034
DOI: doi:10.1145/2213977.2214034
Pages: 615 - 623
Type of Material: Conference Article
Journal/Proceeding Title: 44th Annual ACM Symposium on Theory of Computing, STOC '12
Version: Author's manuscript

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.