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:

"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..

• I'm wondering if "monotonically increasing" might be a useful property. Commented Nov 26, 2013 at 17:16
• The first problem the authors tries to solve in the Necklaces paper is monotonically increasing. It's likely there is no known algorithm that performs better than the general case. Commented Nov 26, 2013 at 17:41