We can do convolution in $O(nlgn)$ for plus/multiply polynomials with fft.  However the approach doesn't seem very generalisable to rings in general. Has there been any progress over the naive $O(n^2)$ convolution for the max/plus ring? 
Complexity of convolution in the max/plus ring
algebra;polynomials;fft;convolution
There is a more general question on mathoverflow. I asked a similar question on CS.SE. jbapple provided a good answer. To quoteNecklaces, Convolutions, and X+Y, By Bremner et  al. shows a  $O\left(\frac{n^2(\lg \lg n)^3}{\lg^2 n}\right)$ algorithm  for this problem on the real RAM and a $O(n \sqrt{n})$ algorithm in  the nonuniform linear decision tree model.Any improvement to this bound will shed light to a few tough open problems like sorting $X+Y$ and all pair shortest path.If one of the function is convex/concave, we can solve the problem in $O(n\log n)$ time. See Speeding up Dynamic Programming, By Eppstein et al..