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...
| Pubblicato in: | Journal of the ACM 51, 3 (2004). |
|---|---|
| Autore principale: | |
| Natura: | Articolo |
| Lingua: | inglese |
| Soggetti: |