Multi-linear formulas for permanent and determinant are of super-polynomial size
Ran Raz · Journal of the ACM · 2004
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 x 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.