# 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)})$$.

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