Separating multilinear branching programs and formulas

Zeev Dvir, Guillaume Malod, Sylvain Perifel, Amir Yehudayoff

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

29 Scopus citations


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
Number of pages9
StatePublished - 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


Other44th Annual ACM Symposium on Theory of Computing, STOC '12
Country/TerritoryUnited States
CityNew York, NY

All Science Journal Classification (ASJC) codes

  • Software


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


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

Cite this