loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
The 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS'02)
Lower Bounds on the Bounded Coefficient Complexity of Bilinear Maps
Vancouver, BC, Canada
November 16-November 19
ISBN: 0-7695-1822-2
Peter Bürgisser, University of Paderborn
Martin Lotz, University of Paderborn
We prove lower bounds of order n log n for both the problem to multiply polynomials of degree n, and to divide 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 to multiply 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.
Citation:
Peter Bürgisser, Martin Lotz, "Lower Bounds on the Bounded Coefficient Complexity of Bilinear Maps," focs, pp.659, The 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS'02), 2002
Usage of this product signifies your acceptance of the Terms of Use.