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

Disgrifiad llawn

Manylion Llyfryddiaeth

Cyhoeddwyd yn:	Journal of the ACM 51, 3 (2004).
Prif Awdur:	Bürgisser, Peter
Fformat:	Erthygl
Iaith:	English
Pynciau:	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.