Bounded tropical decomposition width forces modular subpolynomials to be convex, which yields faster min-plus convolution algorithms for multiple sequences and new Multiple-Choice Knapsack bounds.
Polynomials over idempotent semifields
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
We study univariate polynomials with coefficients in an idempotent semifield and their factorization. We do not assume the idempotent semifield under consideration to be totally ordered, in contrast with most of the existing work on this topic. We notably determine when a polynomial splits into linear factors, and when its associated polynomial function does so. These results lead us to characterize algebraically closed idempotent semifields -- those in which every polynomial function splits. We prove in particular that every complete idempotent semifield is algebraically closed. We also relate algebraic closedness to the properties of preradicability and radicability and to the existence of solutions to polynomial equations or inequalities.
fields
cs.CC 1years
2026 1verdicts
CONDITIONAL 1representative citing papers
citing papers explorer
-
On the Structure of $(\min,+)$ Convolution
Bounded tropical decomposition width forces modular subpolynomials to be convex, which yields faster min-plus convolution algorithms for multiple sequences and new Multiple-Choice Knapsack bounds.