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 language | English (US) |
---|---|
Article number | 8 |
Journal | Journal of the ACM |
Volume | 56 |
Issue number | 2 |
DOIs | |
State | Published - Apr 1 2009 |
Externally published | Yes |
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