10
$\begingroup$

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

|cite|improve this question
$\endgroup$
11
$\begingroup$

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

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ Thank you. I also enjoyed reading about this on the mathoverflow link. $\endgroup$ – Thomas Ahle Nov 26 '13 at 17:13
  • $\begingroup$ I'm wondering if "monotonically increasing" might be a useful property. $\endgroup$ – Thomas Ahle Nov 26 '13 at 17:16
  • 2
    $\begingroup$ 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. $\endgroup$ – Chao Xu Nov 26 '13 at 17:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.