Lower Bounds on the Bounded Coefficient Complexity of Bilinear Maps

Peter Buergisser, Martin Lotz

We prove lower bounds of order $n\log n$ for both the problem to multiply polynomials of degree $n$, and to divide polynomials with remainder, in the model of bounded coefficient a…