Complexity of convolution in the max/plus ring
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..