2003/01/16 by Peter Buergisser, Martin Lotz, Buergisser, Peter +2
Computer Science · Mathematics · Medicine · #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Drug Transport and Resistance Mechanisms #F1.1 #F2.1 #FOS: Computer and information sciences #I.1.2 #Tensor decomposition and applications #cs.CC
paper · pdf · doi:10.48550/arxiv.cs/0301016
19 pages
arxiv created 2003/01/16 · openalex publication_date 2003/01/16 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We prove lower bounds of order nlog 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. 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.