Access Restriction

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

   Open content in new tab
Source: ACM Digital Library