Lower bounds on the bounded coefficient complexity of bilinear mapsLower bounds on the bounded coefficient complexity of bilinear maps

Access Restriction
Subscribed

 Author Brgisser, Peter ♦ Lotz, Martin Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2004 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Algebraic complexity ♦ Bilinear circuits ♦ Lower bounds ♦ Singular values Abstract We prove lower bounds of order $\textit{n}$ log $\textit{n}$ for both the problem of multiplying polynomials of degree $\textit{n},$ and of dividing polynomials with remainder, in the model of bounded coefficient arithmetic circuits over the complex numbers. These lower bounds are optimal up to order of magnitude. The proof uses a recent idea of R. Raz [Proc. 34th STOC 2002] proposed for matrix multiplication. It reduces the linear problem of multiplying a random circulant matrix with a vector to the bilinear problem of cyclic convolution. We treat the arising linear problem by extending J. Morgenstern's bound [J. ACM 20, pp. 305--306, 1973] in a unitarily invariant way. This establishes a new lower bound on the bounded coefficient complexity of linear forms in terms of the singular values of the corresponding matrix. In addition, we extend these lower bounds for linear and bilinear maps to a model of circuits that allows a restricted number of unbounded scalar multiplications. 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 2004-05-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 51 Issue Number 3 Page Count 19 Starting Page 464 Ending Page 482

Open content in new tab

Source: ACM Digital Library