direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Page Content

There is no English translation for this web page.

Ehemalige Mitarbeiter

Prof. Dr. Martin Lotz


Mathematics Institute
Zeeman Building
University of Warwick
Coventry CV4 7AL
United Kingdom
Persönliche Homepage

Publikationen in der Arbeitsgruppe

Lower Bounds on the Bounded Coefficient Complexity of Bilinear Maps
Citation key BL-Lower-Bounds-On-The-Bounded-Coefficient-Complexity-Of-Bilinear-Maps-1
Author Peter Bürgisser and Martin Lotz
Title of Book In Proceedings of 43rd FOCS
Pages 658-668
Year 2002
Address Vancouver
Month November 16-19
Abstract We prove lower bounds of order nłog 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.
Link to publication Link to original publication Download Bibtex entry

Zusatzinformationen / Extras

Quick Access:

Schnellnavigation zur Seite über Nummerneingabe

Auxiliary Functions

This site uses Matomo for anonymized webanalysis. Visit Data Privacy for more information and opt-out options.