Lower bounds on the bounded coefficient complexity of bilinear maps

Peter Bürgisser, Martin Lotz

    Research output: Contribution to journalArticlepeer-review


    We prove lower bounds of order n log n for both the problem of multiplying polynomials of degree 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.
    Original languageEnglish
    Pages (from-to)464-482
    Number of pages18
    JournalJournal of the ACM
    Issue number3
    Publication statusPublished - May 2004


    • Algebraic complexity
    • Bilinear circuits
    • Lower bounds
    • Singular values


    Dive into the research topics of 'Lower bounds on the bounded coefficient complexity of bilinear maps'. Together they form a unique fingerprint.

    Cite this