Convolution without FFT What is the best upper and lower bound known for convolution without FFT? 

Is FFT proven to be essential for time complexity reduction? 
Is cancellation essential as well?
Take a look at Toom-Cook multiplication and see if that is helpful for what you need. The complexity is $O(n^{1+\epsilon})$ for any fixed $\epsilon&gt;0$.