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

• – Chao Xu Nov 26 '13 at 12:02
• @ChaoXu comment -> answer? – Sasho Nikolov Nov 26 '13 at 14:18

There is a more general question on mathoverflow.

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