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