<p>There is a more general question on <a href="https://mathoverflow.net/questions/10237/does-the-convolution-theorem-apply-to-weaker-algebraic-structures/">mathoverflow</a>, and I asked a <a href="https://cs.stackexchange.com/questions/18211/maxima-of-diagonals-in-a-column-wise-and-row-wise-sorted-matrix">similar question on CS.SE</a>. jbapple provided a good answer. To quote:</p>
<blockquote>
<p><a href="http://arxiv.org/abs/1212.4771" rel="nofollow noreferrer">&quot;Necklaces, Convolutions, and X+Y&quot;, By Bremner et
al.</a> shows a
<span class="math-container">$O\left(\frac{n^2(\lg \lg n)^3}{\lg^2 n}\right)$</span> algorithm
for this problem on the real RAM and a <span class="math-container">$O(n \sqrt{n})$</span> algorithm in
the nonuniform linear decision tree model.</p>
</blockquote>
<p>Any improvement to this bound will shed light to a few tough open problems like sorting <span class="math-container">$X+Y$</span> and all pair shortest path.</p>
<p>If one of the functions is convex/concave, we can solve the problem in <span class="math-container">$O(n\log n)$</span> time. See <a href="http://www.ics.uci.edu/%7Eeppstein/pubs/EppGalGia-FOCS-88.pdf" rel="nofollow noreferrer">&quot;Speeding up Dynamic Programming&quot;, By Eppstein et al.</a>.</p>

CC BY-SA 3.0
2013-11-26T17:16:58.367Z
I'm wondering if "monotonically increasing" might be a useful property.
Thomas Ahle
CC BY-SA 3.0
2013-11-26T17:41:52.430Z
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.
Chao Xu
CC BY-SA 4.0
2013-11-26T17:03:36.537Z
2021-01-09T17:45:11.980Z
2021-01-09T17:45:11.980Z
Chao Xu
<p>We can do convolution in <span class="math-container">$O(n\log n)$</span> 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 <span class="math-container">$O(n^2)$</span> convolution for the max/plus ring?</p>

<p>I should note that one can transform soft-max/plus into plus/product by doing exponentiation. Here <span class="math-container">$\text{soft-max}(x,y)=\log(e^x+e^y) = \max(x,y)  + \log(1+e^{\min(x,y)-\max(x,y)})$</span>.</p>

<algebra><polynomials><fft><convolution>
Complexity of convolution in the max/plus ring
Thomas Ahle
# Complexity of convolution in the max/plus ring

(Asked by: username_0 on 2013-11-26)

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

**Tags:** algebra, polynomials, fft, convolution


---

## 1 answers

### Answer by username_1 on 2013-11-26. Score: 12 | Accepted answer

There is a more general question on [mathoverflow](https://mathoverflow.net/questions/10237/does-the-convolution-theorem-apply-to-weaker-algebraic-structures/), and I asked a [similar question on CS.SE](https://cs.stackexchange.com/questions/18211/maxima-of-diagonals-in-a-column-wise-and-row-wise-sorted-matrix). jbapple provided a good answer. To quote:

> ["Necklaces, Convolutions, and X+Y", By Bremner et
> al.](http://arxiv.org/abs/1212.4771) 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.](http://www.ics.uci.edu/%7Eeppstein/pubs/EppGalGia-FOCS-88.pdf).

> **Comments:**
> **username_0**: I'm wondering if "monotonically increasing" might be a useful property.  
> **username_1**: 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.  

---

