direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Ehemalige Mitarbeiter

Dr. Martin Lotz

Lupe

Kontakt
School of Mathematics
Alan Turing Building
Oxford Road
The University of Manchester
Manchester, M139PL
United Kingdom
 
Persönliche Homepage
www.maths.manchester.ac.uk/~mlotz/

Publikationen in der Arbeitsgruppe

Lower Bounds on the Bounded Coefficient Complexity of Bilinear Maps
Zitatschlüssel BL-Lower-Bounds-On-The-Bounded-Coefficient-Complexity-Of-Bilinear-Maps
Autor Peter Bürgisser and Martin Lotz
Seiten 464-482
Jahr 2004
Journal Journal of the ACM
Jahrgang 51
Nummer 3
Zusammenfassung 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 zur Publikation Link zur Originalpublikation Download Bibtex Eintrag

Zusatzinformationen / Extras

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe