{"id":"3f9b9d24-1d5d-4594-b794-19fbe54310d3","arxiv_id":"2608.13310","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"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.","lead":"This paper introduces tropical decomposition width, a parameter measuring how finely a tropical polynomial factors into low-degree pieces, and uses it to design faster algorithms for min-plus convolution of multiple sequences. It also proves structural convexity theorems and interpolation lower bounds that tie the difficulty of min-plus convolution to algebraic rigidity.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4.14's proof does not justify that the stored split point equals the isolated solution's split point; without this invariant, the Hoeffding window bound may not apply.","rationale":"The reader's weakest-assumption diagnosis points at the shuffle-isolation interaction in Theorem 4.14, and that is indeed the most load-bearing soft spot in the paper. A more precise formulation of the concern is that the proof never spells out why the stored split point from the previous output index is the split point of the isolated solution. Without that invariant, the Hoeffding bound on the prefix sums of q-p does not by itself control |q_split - ps|, because ps could be an arbitrary optimal split for d_{t-1} that differs from p_split by an unbounded zero-sum adjustment. This is not a fatal flaw: the invariant can likely be established by induction, since the isolated solution is the unique lexicographic minimum and any scan containing its split point will store exactly that split. The central modular convexity theorems (Theorems 3.20 and 3.22) appear internally consistent, and the deterministic algorithms' analyses are detailed. The randomized multiple-sequence proof is the one place where a needed inductive hypothesis is missing, which matches the reader's conditional verdict. A careful rewrite of Part 2 of Theorem 4.14 should either add the invariant or explicitly justify that ps and p_split coincide; until then, the proof of the headline randomized bound has a gap.","tokens_in":46494,"tokens_out":24097,"duration_ms":279292,"concrete_test":"Re-derive Part 2 of Theorem 4.14 with the explicit invariant: before processing d_t, the stored split point ps equals the split point of the isolated solution p for d_{t-1}. Verify the base case at d_1 (where the optimal split is unique) and the transition: if the scan at d_{t-1} is guaranteed to contain p_split, then uniqueness of the lexicographic minimum forces ps = p_split. If this invariant cannot be established, construct a small concrete instance with two optimal splits for d_{t-1} whose left-half sums differ by more than U and check whether the algorithm's scan can still miss the isolated split for d_t; such an example would show the proof gap is real rather than merely cosmetic.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In Part 2 of Theorem 4.14, the proof fixes p and q as the isolated lexicographic solutions for consecutive finite output indices d_{t-1} and d_t in a recursive merge, and bounds the split-point difference by prefix sums of the shuffled difference q-p. The argument then asserts that this controls the difference between q's split point and the stored split point ps from the previous iteration. This is not justified as written: the algorithm's stored ps is whatever optimal split was found during the previous scan, and the proof only assumes the previous output value was computed correctly (event P_{t-1}), not that ps equals the split point of p. Two different optimal splits for the same output index can differ by an arbitrary zero-sum adjustment over the left half, so |ps - p_split| need not be bounded by U without an explicit invariant. If ps is far from p_split, then q's split point can lie outside the scanned window even when all prefix sums of q-p are bounded, and correctness at d_t is not established. The gap is repairable by strengthening the induction invariant to say that after processing d_{t-1}, the stored split point is exactly the split of the isolated solution for d_{t-1}, using uniqueness of the lexicographic minimum to force the scan to store that split whenever it is in the window. The paper does not state or prove this invariant, and the analysis of the O(k n^2 sqrt(min(k,n)) log^{1.5}(kn)) algorithm depends on it.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies (min,+) convolution through tropical polynomials, where convolution is polynomial multiplication. It introduces a new parameter, tropical decomposition width (tdw), and proves two modular convexity theorems (Theorems 3.20 and 3.22): bounded tdw forces bounded convex gap on arithmetic subpolynomials, and, when lcm_{i=1}^k i divides the modulus, it forces full convexity. From these it derives deterministic convolution algorithms for low-width sequences (Theorems 4.4 and 4.7), a randomized Multiple-Sequence (min,+) Convolution algorithm (Theorem 4.14), a single-entry variant (Theorem 4.15), conditional lower bounds (Theorem 4.17), and new bounds for Multiple-Choice Knapsack. The final sections give algebraic results on interpolation algebras for bounded-tdw classes and prove that tdw is invariant under flat T-algebra extensions (Theorem 5.16).","tokens_in":46745,"tokens_out":29016,"duration_ms":293340,"significance":"The structural results are the paper's strongest contribution: the modular convexity theorems are parameter-free, are proved from explicit additive-combinatorics lemmas, and have clean algorithmic consequences for low tropical decomposition width. The deterministic algorithms (Theorem 4.4 and Theorem 4.7) are self-contained and appear correct; the interpolation-algebra lower bound (Theorem 5.6) and the flatness invariance theorem (Theorem 5.16) are also notable and well argued. If the randomized Multiple-Sequence Convolution theorem could be repaired, the paper would give the first improvement over quadratic scaling for multiple sequences and would connect naturally to recent knapsack progress. However, as written, the proof of Theorem 4.14 has a load-bearing gap concerning the proximity of the isolated solutions used in the concentration argument, so the headline randomized bound is not yet established.","major_comments":[{"comment":"The inference 'Since d_t−d_{t−1}≤n, Lemma 4.3 gives D(p,q)≤2n' is invalid as stated. Lemma 4.3 asserts that for any solution r of one output index there exists some solution of the other output index within distance 2n; it does not assert that the unique isolated solution q of d_t is within 2n of the isolated solution p of d_{t−1}. Because the isolation weights are chosen independently per entry, an optimal solution with many changed coordinates can be the weight-minimal one even when a close optimal solution exists. Consequently the subsequent bound z≤min(k,2n), on which both the Hoeffding step and the window radius U rely, is unsupported. This is not a presentation issue: the claimed running time O(k n^2 sqrt(min(k,n)) log^{1.5}(kn)) depends on it. A repair requires a proximity statement for the specific tie-broken solutions used by the recursion, or a modified isolation/canonical-solution argument.","section":"§4.2, Theorem 4.14, Parts 2-3"},{"comment":"The claim that 'the split point q of the isolated optimum for d_t differs from the stored split point ps for d_{t−1} by one of the prefix sums of the shuffled difference sequence' is not justified by the induction as written. The event P_{t−1} only asserts that the output value at d_{t−1} is correct; it does not assert that the stored split point from the scan equals the split coordinate of the isolated solution p. Two different optimal splits for the same output index can differ by an arbitrary zero-sum adjustment over the left half, so |ps − p_split| need not be bounded. Without the explicit invariant that after processing d_{t−1} the stored split is exactly the split of the isolated solution for d_{t−1}, boundedness of the prefix sums of q−p does not imply that q's split lies in the scanned window. Such an invariant is plausible because lexicographic uniqueness would force the scan to store that split whenever it is in the window, but it is not stated or proved in the paper.","section":"§4.2, Theorem 4.14, Parts 2-3"}],"minor_comments":[{"comment":"The statement 'z=|I|≤min(k,2n)' is not justified. I is the set of indices appearing in any retained S_Δ, and a single index can appear for many Δ values, so |I| can be as large as min(k, O(n^2)). The subsequent Hoeffding step only needs the number of nonzero adjusted coordinates |J|≤2n, so the proof should be rewritten using this distinction.","section":"§4.2, Theorem 4.15"},{"comment":"Definition 2.12 writes a tropical decomposition as a sum over factors, whereas the introduction uses product notation for the same operation. The two agree under the paper's convention (min for ⊕ and + for ⊗), but the text should state this explicitly to avoid an apparent inconsistency.","section":"Definition 2.12"},{"comment":"Algorithm 3 says to pick the smallest k such that every sequence in MS_k(a) or MS_k(b) is convex, but it does not specify how this k is computed. Since checking a candidate k costs O(|a|+|b|) time, trying k=1,...,L can be absorbed into the stated bound, but the implementation should be described.","section":"Algorithm 3"}],"recommendation":"major_revision","confidential_remarks":"The deterministic structural results (Theorems 1.1-1.4, 1.6, and the algebraic results of Section 5) appear sound and are the strongest part of the manuscript. The main risk is the proof of Theorem 4.14: the proximity of the isolated solutions and the stored-split invariant are both missing, and these are load-bearing for the headline Multiple-Sequence Convolution bound. I would not accept the paper until that proof is repaired. The unusual citation [Gri26] to a GPT-generated proof is not used in a load-bearing way, but the editors may wish to verify its status."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper is worth your time. It introduces tropical decomposition width, proves two modular convexity theorems, and shows they yield deterministic convolution algorithms with complexity depending on that width. Those parts are the real contribution, and on my reading the central argument holds up: the additive-combinatorics lemmas are original, the proof of Theorem 3.22 is sound, and the deterministic algorithms (Theorems 1.3 and 1.4) follow cleanly from the structural results. The interpolation algebra results in Section 5 are also genuinely new and connect the algorithmic questions to algebraic rigidity in a way I have not seen before.\n\nThe soft spots are concentrated in Section 4.2. The randomized multiple-sequence algorithm has a plausible but under-specified analysis. In Theorem 4.14, the proof assumes that the stored split point from the previous output index is the split point of the isolated solution for that index, so that the Hoeffding prefix-sum bound controls the distance to the next isolated solution. The text only proves that the previous value was computed correctly; it does not prove that the stored split point is the isolated solution's split point. If different optimal splits are possible, the stored ps could drift away, and the window bound would not apply. This is a real gap in the proof as written, though I suspect it is repairable by strengthening the induction invariant and using lexicographic uniqueness of the isolated solution. I would want a referee to see that repair before trusting the O(k n^2 sqrt(min(k,n)) polylog) claim.\n\nTwo smaller things: Definition 2.12 uses a summation sign where the introduction uses product notation, which is confusing even if the intended meaning is clear. And the reference [Gri26] to a GPT-5.5-produced result looks like a placeholder or a joke; in a serious paper that citation should be replaced or justified.\n\nThe deterministic results and the structural theorems are solid enough that the paper deserves a careful referee, and the weaknesses I found are not fatal to the main narrative. This is a paper I would bring to a reading group to discuss the multiple-sequence analysis, and I would cite the modular convexity theorems in future work.","headline":"A serious new structural framework for min-plus convolution; the randomized multiple-sequence algorithm has an unresolved split-point invariant that a referee should push on.","tokens_in":47259,"tokens_out":1612,"would_cite":true,"duration_ms":20695,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["16Y60","14T10","68Q25","68Q17"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper introduces tropical decomposition width and proves that bounded width forces modular convexity, which yields faster algorithms for (min,+) convolution and its multi-sequence version.","keywords":["min-plus convolution","tropical polynomial","tropical decomposition width","modular convexity","multiple-sequence convolution","interpolation algebra","multiple-choice knapsack","fine-grained complexity"],"falsifier":"For large $k=n$, run the randomized all-entry algorithm on input sequences with entries in $\\{0,1,\\dots,n^{O(1)}\\}$ chosen from a distribution engineered to concentrate the difference between consecutive optima on one coordinate, and record all prefix sums of the shuffled difference sequence at a merge step; if any prefix sum exceeds $10n\\sqrt{(c+5)\\min(k,2n)\\log(kn)}+n$ with probability noticeably larger than $(kn)^{-c}$, the uniform-random-order premise fails and the claimed $O(kn^2\\sqrt{\\min(k,n)}\\log^{1.5}(kn))$ guarantee loses its proof.","tokens_in":46268,"feed_emoji":"🧮","tokens_out":14729,"duration_ms":146002,"temperature":0.7,"pith_summary":"The paper studies the (min,+) convolution $c_i=\\min_{j+k=i}(a_j+b_k)$, the operation whose quadratic-time barrier is a central open problem in fine-grained complexity, by viewing sequences as tropical polynomials in which convolution is multiplication. Its central object is the tropical decomposition width $\\operatorname{tdw}(A)$: the smallest $k$ such that $A$ is a tropical product of factors of degree at most $k$. The paper proves two modular convexity theorems: every arithmetic subsequence of a low-width polynomial has small convex gap, and when the modulus $L$ is divisible by $\\operatorname{lcm}_{i=1}^k i$, every $L$-step subsequence is exactly convex, with a sharp converse. These theorems are converted into deterministic convolution algorithms, a randomized multiple-sequence convolution algorithm that breaks the natural $O(k^2 n^2)$ bound, new bounds for Multiple-Choice Knapsack, and interpolation-algebra results separating bounded-width classes from general tropical polynomials. A sympathetic reader should take away that the difficulty of (min,+) convolution may be tied to the width rigidity of tropical factorization rather than to the absence of algebraic structure.","feed_headline":"A width parameter decides when min-plus convolution speeds up","feed_subtitle":"Bounded tropical decomposition width forces convexity, unlocking faster deterministic and multi-sequence convolution.","key_machinery":"The load-bearing object is the tropical decomposition width, defined for a tropical polynomial $A=\\min_i(a_i+ix)$ as the smallest $k$ for which $A$ is a finite tropical product of factors of degree at most $k$. Around it the paper builds: modular arithmetic subpolynomial sets $\\operatorname{MS}_L(A)$, whose $r$-th member samples coefficients at indices $r, r+L, r+2L,\\dots$; the convex gap $\\operatorname{cgap}(B)$, the largest gap between adjacent points of the lower convex support of $B$; additive-combinatorial lemmas bounding the function $F(m,k)$ needed to find zero-sum submultisets; an adjustment lemma bounding how far a solution for one output index must move to solve a nearby index; and a linear-time merge algorithm that produces a weak convex support sequence of a product from the convex support sequences of its factors. For the algebraic half, the cyclic tropical polynomial semiring $T[y]/\\langle(\\operatorname{lcm}_{i=1}^k i)y\\sim 0\\rangle$ serves as the finite-rank interpolation algebra for the width-$k$ class.","core_discovery":"The paper's discovery is that bounded tropical decomposition width forces a strong, modular form of convexity in the coefficient sequence. The second modular convexity theorem states that if $L$ is divisible by $\\operatorname{lcm}_{i=1}^k i$, then for every tropical polynomial $A$ with $\\operatorname{tdw}(A)\\le k$, every arithmetic subpolynomial in $\\operatorname{MS}_L(A)$ is convex; and if that divisibility fails, a width-$k$ polynomial exists with a non-convex $L$-modular subpolynomial. The same structure, via an adjustment lemma bounding how optimal solutions change between nearby outputs, drives the deterministic $O(n\\max(\\operatorname{tdw}(a),\\operatorname{tdw}(b))^2)$ algorithm and the $O(n e^{\\min(\\operatorname{tdw}(a),\\operatorname{tdw}(b))(1+o(1))})$ algorithm. The randomized multiple-sequence algorithm extends the adjustment argument over a lexicographic lifting of the tropical semiring, using isolation to make optima unique and a shuffle to make the differences between consecutive optima concentrate. If the theorems are right, min-plus convolution on structured instances is no longer quadratic, and the multi-sequence version, unlike the two-sequence version, admits an exponent break.","pith_inferences":["If the random shuffle stage in the multiple-sequence algorithm could be derandomized, the multi-sequence convolution bound would become deterministic with the same exponent, further separating multi-sequence complexity from two-sequence hardness.","The lcm criterion suggests a number-theoretic hierarchy worth testing elsewhere: divisibility of the modulus by $\\operatorname{lcm}_{i=1}^k i$ controls convexity, so algorithms based on modular convexity may transfer to other tropical optimization problems with small lcm structure.","Because the paper leaves open the complexity of computing $\\operatorname{tdw}$ itself, an efficient approximation of the width could turn the width-promise algorithms into general-purpose convolution algorithms.","The flat-extension invariance suggests a rigidity principle: tropical polynomials resist refined factorization over extension semirings, which may explain why algebraic transform methods for classical $(+,\\times)$ convolution do not transfer."],"forward_implications":["If the width bound $k$ is supplied, two-sequence convolution is deterministically computed in $O(n k^2)$ time, so instances whose coefficient sequences factor into low-degree tropical factors are no longer quadratic.","Without a supplied bound, convolution runs in $O(n e^{k(1+o(1))})$ time whenever one input has width $k$, which is subquadratic for $k=o(\\log n)$.","The all-entry Multiple-Sequence Convolution runs in $O(k n^2 \\sqrt{\\min(k,n)} \\log^{1.5}(kn))$ randomized time, improving the natural $O(k^2 n^2)$ bound for balanced $k$ and $n$.","Multiple-Choice Knapsack inherits improved bounds in the $(n,w_{\\max})$ parameterization, with single-entry and all-entry versions both faster than the previous best in the small-maximum-weight regime.","No evaluation-interpolation algebra can deliver a subquadratic general convolution algorithm, because separating degree-$n$ tropical polynomials requires generating rank at least $\\lfloor n/2\\rfloor+1$."],"supporting_citations":[{"why":"Supplies the totally monotone matrix-searching subroutine used to convolve convex sequences in linear time.","marker":"[AKMSW87]"},{"why":"Provides the sampling-without-replacement concentration inequality used to bound prefix sums after the random shuffle.","marker":"[Hoe63]"},{"why":"Provides the isolation lemma that makes the optimum for each target unique before the shuffle.","marker":"[MVV87]"},{"why":"Supplies the weak tropical Nullstellensatz used to prove invariance of tropical decomposition width under flat extensions.","marker":"[AR17]"},{"why":"Defines the (min,+) convolution hypothesis and the knapsack lower-bound reductions used for the conditional lower bounds.","marker":"[CMWW19]"},{"why":"Contributes the random-shuffle technique for knapsack that the multiple-sequence algorithm adapts.","marker":"[HX24]"},{"why":"Provides the Chebyshev estimate $\\psi(k)=k+o(k)$ used to turn the lcm bound into the $e^{k(1+o(1))}$ running time.","marker":"[Apo76]"}],"fun_headline_variants":["Tropical width forces convexity, speeding up min-plus convolution","Min-plus convolution: width parameter decides speedup","Bounded width unlocks faster min-plus convolution algorithms","New speedups for min-plus convolution via tropical width","Width parameter gives min-plus convolution a speed boost"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The randomized multiple-sequence bound depends on the premise that after randomly permuting the sequences, the nonzero coordinate differences between consecutive isolated optima appear in uniformly random order, so that every prefix sum of those differences stays within the announced window with high probability.","fun_headline_variants_meta":{"raw":{"variants":["Tropical width forces convexity, speeding up min-plus convolution","Min-plus convolution: width parameter decides speedup","Bounded width unlocks faster min-plus convolution algorithms","New speedups for min-plus convolution via tropical width","Width parameter gives min-plus convolution a speed boost"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000325,"raw_usage":{"total_tokens":1904,"prompt_tokens":1108,"completion_tokens":796,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":724,"completion_tokens_details":{"reasoning_tokens":721}},"tokens_in":724,"tokens_out":796,"duration_ms":7962,"temperature":1.0,"reasoning_tokens":721,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T14:02:18.319280+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For large $k=n$, run the randomized all-entry algorithm on input sequences with entries in $\\{0,1,\\dots,n^{O(1)}\\}$ chosen from a distribution engineered to concentrate the difference between consecutive optima on one coordinate, and record all prefix sums of the shuffled difference sequence at a merge step; if any prefix sum exceeds $10n\\sqrt{(c+5)\\min(k,2n)\\log(kn)}+n$ with probability noticeably larger than $(kn)^{-c}$, the uniform-random-order premise fails and the claimed $O(kn^2\\sqrt{\\min(k,n)}\\log^{1.5}(kn))$ guarantee loses its proof.","supporting_citations":[],"review_version":1}