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

Research output: Contribution to journalConference article

40 Scopus citations

Abstract

An arithmetic formula is multi-linear if the polynomial computed by each of its sub-formulas is multi-linear. We prove that any multi-linear 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 multi-linear formulas of constant depth.

Original languageEnglish (US)
Pages (from-to)633-641
Number of pages9
JournalConference Proceedings of the Annual ACM Symposium on Theory of Computing
DOIs
StatePublished - 2004
Externally publishedYes
EventProceedings of the 36th Annual ACM Symposium on Theory of Computing - Chicago, IL, United States
Duration: Jun 13 2004Jun 15 2004

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Algebraic complexity
  • Arithmetic formulas
  • Circuit complexity
  • Computational 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