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

Ran Raz

doi:10.1145/1007352.1007353

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

Ran Raz

Research output: Contribution to journal › Conference article › peer-review

41 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 language	English (US)
Pages (from-to)	633-641
Number of pages	9
Journal	Conference Proceedings of the Annual ACM Symposium on Theory of Computing
DOIs	https://doi.org/10.1145/1007352.1007353
State	Published - 2004
Externally published	Yes
Event	Proceedings of the 36th Annual ACM Symposium on Theory of Computing - Chicago, IL, United States Duration: Jun 13 2004 → Jun 15 2004

All Science Journal Classification (ASJC) codes

Software

Keywords

Algebraic complexity
Arithmetic formulas
Circuit complexity
Computational complexity
Lower bounds

Access to Document

10.1145/1007352.1007353

Cite this

@article{899942c139324f75b9c1d4bd3fffcf2f,

title = "Multi-linear formulas for permanent and determinant are of super-Polynomial size",

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.",

keywords = "Algebraic complexity, Arithmetic formulas, Circuit complexity, Computational complexity, Lower bounds",

author = "Ran Raz",

year = "2004",

doi = "10.1145/1007352.1007353",

language = "English (US)",

pages = "633--641",

journal = "Conference Proceedings of the Annual ACM Symposium on Theory of Computing",

issn = "0734-9025",

publisher = "Association for Computing Machinery (ACM)",

note = "Proceedings of the 36th Annual ACM Symposium on Theory of Computing ; Conference date: 13-06-2004 Through 15-06-2004",

}

TY - JOUR

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

AU - Raz, Ran

PY - 2004

Y1 - 2004

N2 - 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.

AB - 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.

KW - Algebraic complexity

KW - Arithmetic formulas

KW - Circuit complexity

KW - Computational complexity

KW - Lower bounds

UR - https://www.scopus.com/pages/publications/4544258177

UR - https://www.scopus.com/pages/publications/4544258177#tab=citedBy

U2 - 10.1145/1007352.1007353

DO - 10.1145/1007352.1007353

M3 - Conference article

AN - SCOPUS:4544258177

SN - 0734-9025

SP - 633

EP - 641

JO - Conference Proceedings of the Annual ACM Symposium on Theory of Computing

JF - Conference Proceedings of the Annual ACM Symposium on Theory of Computing

T2 - Proceedings of the 36th Annual ACM Symposium on Theory of Computing

Y2 - 13 June 2004 through 15 June 2004

ER -

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

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this