Multi-linear formulas for permanent and determinant are of super-polynomial size

Research output: Contribution to journalArticlepeer-review

91 Scopus citations


An arithmetic formula is multilinear if the polynomial computed by each of its subformulas is multilinear. We prove that any multilinear arithmetic formula for the permanent or the determinant of an n × n matrix is of size super-polynomial in n. Previously, super-polynomial lower bounds were not known (for any explicit function) even for the special case of multilinear formulas of constant depth.

Original languageEnglish (US)
Article number8
JournalJournal of the ACM
Issue number2
StatePublished - Apr 1 2009
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Hardware and Architecture
  • Artificial Intelligence


  • Algebraic complexity
  • Arithmetic formulas
  • Circuit complexity
  • Lower bounds


Dive into the research topics of 'Multi-linear formulas for permanent and determinant are of super-polynomial size'. Together they form a unique fingerprint.

Cite this