Subquadratic multiplication of polynomials in the max-plus/tropical semiring

Is there an algorithm to multiply two polynomials with coefficients in the max-plus semiring $$(\mathbb{Z}\cup\{-\infty\}, \max, +)$$ which is faster than the trivial one? I'm interested in the coefficients of the product, so I can't ignore the differences between two polynomials which specify the same function. This makes some nice results like the fundamental theorem of algebra (for the tropical semiring) not immediately useful.

The obvious candidates like Karatsuba don't work (the Grothendieck group of $$(\mathbb{Z}\cup\{-\infty\}, \max)$$ is trivial, so you can't extend the semiring to a ring), but I also haven't been able to come up with a reason why it shouldn't possible.

You can assume the coefficients are monotonically increasing if it makes the algorithm easier/faster.

• I believe that the ordered property might allow for a $O(n+m)$ algorithm. You can discover it by considering two polynomials ($\sum \alpha_i x^i, \sum \beta_j x^j$) with ordered coefficients and drawing a table where the rows are the coefficients of $(\sum \alpha_i x^i) \cdot \beta_j x^j$ (the table columns should be $x^{2n},...,x^0$). Now notice that you can precompute the prefix sums of $\alpha_n,...,\alpha_0,$ and $\beta_n,...,\beta_0$. Notice that the columns will always be made of a subarray of $\alpha$ and a subarray of $\beta$ thus you can use the prefix sums to compute them. Commented Mar 13, 2023 at 21:40
• If you use binary search for each row to determine the index at which $\beta_j > \alpha_i$ the algorithm takes $O((n+m)\log(n))$, but since the $\beta$ and $\alpha$ are ordered, you can use the two-pointer method for that. Commented Mar 13, 2023 at 21:44

The problem is computing the array $$C$$ defined as $$C_i = \max_{j+k=i} (A_j + B_k)$$ given arrays $$A$$ and $$B$$. It is called the max-plus convolution, or MaxConv problem. Note that the equivalent min-plus convolution problem is also used in literature.

There is a sub-quadratic time reduction from the 3SUM problem to this problem [1]. The popular 3SUM conjecture states there is no truly sub-quadratic ($$O(n^{2-\epsilon})$$ for $$\epsilon > 0$$) algorithm for the 3SUM problem. Therefore, no truly sub-quadratic algorithm is known for the max-plus convolution problem.

If the arrays are monotone, and all values are integers bounded by $$O(n)$$, subquadratic algorithms are known. Recently, Chi et al. [2] presented an $$\tilde{O}(n^{1.5})$$-time algorithm for this problem. Note that "monotonically increasing" and "monotonically decreasing" variants are equivalent because we can reverse both arrays as well as the resulting array.

Building upon the previous answer by pcpthm, the monotone case has been recently generalized to the case when the entries are bounded by a parameter $$W$$. In this case, the running time amounts to $$\tilde O(n \sqrt{W})$$ [1]; the notation $$\tilde O$$ hides $$\mathrm{polylog}$$ factors.

Another algorithm you might be interested in is the simple bounded-input case, i.e., without any monotonicity assumption. In that case, you can have an $$\tilde O(n W)$$-time algorithm, described in Karol's PhD thesis (Sec. 5.7.2) [2];

[1] Bringmann et al. "Even Faster Knapsack via Rectangular Monotone Min-Plus Convolution and Balancing", https://arxiv.org/abs/2404.05681

[2] Węgrzycki, "Provably Optimal Dynamic Programming". https://www.mimuw.edu.pl/~kw305874/thesis.pdf