Lower bounds on the bounded coefficient complexity of bilinear maps.

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...

Volledige beschrijving

Bibliografische gegevens

Gepubliceerd in:	Journal of the ACM 51, 3 (2004).
Hoofdauteur:	Bürgisser, Peter
Formaat:	Artikel
Taal:	English
Onderwerpen:	Theory of computation. Computation by abstract devices. Models of computation. Analysis of algorithms and problem complexity. Numerical algorithms and problems. Computing methodologies. Symbolic and algebraic manipulation. Algorithms. Theory.