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

Research output: Contribution to journalArticlepeer-review

95 Scopus citations

Abstract

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
Volume56
Issue number2
DOIs
StatePublished - Apr 1 2009
Externally publishedYes

All Science Journal Classification (ASJC) codes

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

Keywords

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

Fingerprint

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