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

Descripción completa

Detalles Bibliográficos

Publicado en:	Journal of the ACM 51, 3 (2004).
Autor principal:	Bürgisser, Peter
Formato:	Artículo
Lenguaje:	English
Materias:	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.