# Complexity of convolution in the max/plus ring

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?

• – 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..