### Multi-linear formulas for permanent and determinant are of super-polynomial sizeMulti-linear formulas for permanent and determinant are of super-polynomial size

Access Restriction
Subscribed

 Author Raz, Ran Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2009 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Algebraic complexity ♦ Arithmetic formulas ♦ Circuit complexity ♦ Lower bounds 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 $\textit{n}$ × $\textit{n}$ matrix is of size super-polynomial in $\textit{n}.$ Previously, super-polynomial lower bounds were not known (for any explicit function) even for the special case of multilinear formulas of constant depth. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2009-04-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 56 Issue Number 2 Page Count 17 Starting Page 1 Ending Page 17

#### Open content in new tab

Source: ACM Digital Library