Complexity of convolution in the max/plus ring We can do convolution in $O(n\log n)$ 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?

I should note that one can transform soft-max/plus into plus/product by doing exponentiation. Here $\text{soft-max}(x,y)=\log(e^x+e^y) = \max(x,y)  + \log(1+e^{\min(x,y)-\max(x,y)})$.
There is a more general question on mathoverflow, and I asked a similar question on CS.SE. jbapple provided a good answer. To quote:

&quot;Necklaces, Convolutions, and X+Y&quot;, 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 functions is convex/concave, we can solve the problem in $O(n\log n)$ time. See &quot;Speeding up Dynamic Programming&quot;, By Eppstein et al..