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?
7
$\begingroup$
$\endgroup$
-
5$\begingroup$ Yes, cs.illinois.edu/~jeffe/pubs/necklace.html $\endgroup$ – Chao Xu Nov 26 '13 at 12:02
-
1$\begingroup$ @ChaoXu comment -> answer? $\endgroup$ – Sasho Nikolov Nov 26 '13 at 14:18
9
$\begingroup$
$\endgroup$
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..
-
$\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
-
1$\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
