Separating multilinear branching programs and formulas

Zeev Dvir, Guillaume Malod, Sylvain Perifel, Amir Yehudayoff

Research output: Chapter in Book/Report/Conference proceedingConference contribution

18 Scopus citations

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 languageEnglish (US)
Title of host publicationSTOC '12 - Proceedings of the 2012 ACM Symposium on Theory of Computing
Pages615-623
Number of pages9
DOIs
StatePublished - Jun 26 2012
Event44th Annual ACM Symposium on Theory of Computing, STOC '12 - New York, NY, United States
Duration: May 19 2012May 22 2012

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Other

Other44th Annual ACM Symposium on Theory of Computing, STOC '12
CountryUnited States
CityNew York, NY
Period5/19/125/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

    Dvir, Z., Malod, G., Perifel, S., & Yehudayoff, A. (2012). Separating multilinear branching programs and formulas. In 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