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.