Pith. sign in

REVIEW 2 major objections 3 minor 30 references

On the Structure of $(\min,+)$ Convolution

T0 review · 2 major / 3 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read 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.

desk verdict 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. read the letter →

arxiv 2608.13310 v1 pith:7DAQQ3JP submitted 2026-08-13 cs.CC cs.DM

Huanyi Zhou This is my paper · ORCID
classification cs.CCcs.DM MSC 16Y6014T1068Q2568Q17
keywords min-plusconvolutiontropicalpolynomialdecompositionwidthmodularconvexitymultiple-sequenceinterpolationalgebramultiple-choiceknapsackfine-grainedcomplexity
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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$.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 3 minor

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).

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 (2)
  1. [§4.2, Theorem 4.14, Parts 2-3] 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.
  2. [§4.2, Theorem 4.14, Parts 2-3] 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.
minor comments (3)
  1. [§4.2, Theorem 4.15] 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.
  2. [Definition 2.12] 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.
  3. [Algorithm 3] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the paper's structural theorems and algorithms are proven from definitions and in-paper lemmas, with no fitted inputs, self-citation chains, or predictions that reduce to their own assumptions.

full rationale

I walked the derivation chain. The central results are the two modular convexity theorems (Theorems 3.20 and 3.22), and these are proven from the additive-combinatorial estimates F(m,k) (Lemmas 3.12, 3.13, 3.16, 3.17; Corollaries 3.18 and 3.19), which are stated and proven inside the paper from elementary pigeonhole and greedy arguments. The algorithms in Section 4 use these theorems as upper-bound tools, not as restatements of the algorithm's correctness: Algorithm 2 invokes Lemma 4.3 (adjustment lemma) and structural closure properties; Algorithm 3 invokes Theorem 3.22 to guarantee convex modular subsequences, and its correctness is then shown directly by the residue-class argument in Theorem 4.7. The randomized Multiple-Sequence algorithm (Theorem 4.14) relies on standard externally cited results: Hoeffding's inequality without replacement and the isolation lemma. These are used as probabilistic tools, and the algorithm's claimed bound is not an input to the structural theorems. I also checked for self-citation load-bearing steps. The paper cites prior work for standard facts (SMAWK, Hoeffding, isolation, tropical Nullstellensatz, Chebyshev estimate), but the main structural claims do not rest on any prior work by the same author or on an imported uniqueness theorem. The one notable proof concern, flagged in the reader's take, is that Theorem 4.14's induction does not explicitly maintain the invariant that the stored split point equals the split point of the isolated solution; this is a potential correctness gap rather than circularity, since it does not make the conclusion equivalent to an assumption or to a fitted value. No fitted constants are present, no empirical patterns are renamed as predictions, and no ansatz is smuggled in via citation. I therefore find no significant circularity.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

No free parameters are fitted to data. The paper introduces new mathematical definitions, such as tropical decomposition width and interpolation algebras, but these are definitions rather than postulated entities requiring independent empirical evidence. All external results are standard or clearly cited.

assumptions (5)
  • domain assumption Real RAM model with unit-cost real arithmetic and low-degree restriction
    Stated in the computational model section; the algorithms' running times assume unit-cost operations on real numbers, citing [CWX22].
  • standard math Hoeffding's inequality for sampling without replacement
    Used in Theorem 4.14 and Theorem 4.15 to bound random prefix sums; cited to [Hoe63].
  • standard math Isolation lemma
    Used to make optimal solutions unique under random tie-breaking weights; cited to [MVV87].
  • domain assumption Weak tropical Nullstellensatz for congruences
    Used in Theorem 5.16 to transfer a decomposition over a flat T-algebra back to T; cited to [AR17].
  • standard math Chebyshev estimate psi(k) = k + o(k)
    Used in Lemma 4.6 to bound lcm_{i=1}^k i as e^{k(1+o(1))}; cited to [Apo76].

how reviews work

0 comments
Cite this review

Pith. "Pith review of On the Structure of $(\min,+)$ Convolution." pith.science (2026). https://pith.science/paper/7DAQQ3JP

@misc{pith2026260813310,
  author       = {Pith},
  title        = {Pith review of: On the Structure of $(\min,+)$ Convolution},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/7DAQQ3JP}},
  note         = {Machine review of arXiv:2608.13310}
}
abstract

The $(\min,+)$ convolution is a central problem in fine-grained complexity, and whether it admits a truly subquadratic algorithm remains open. We study it through tropical polynomials, where $(\min,+)$ convolution is exactly polynomial multiplication. We introduce tropical decomposition width, a parameter measuring how finely a tropical polynomial can be decomposed into low-degree factors. We prove modular convexity theorems showing that bounded tropical decomposition width forces strong convexity on arithmetic subpolynomials. This yields deterministic algorithms for computing $a\otimes b$ in $O(n\max(\operatorname{tdw}(a),\operatorname{tdw}(b))^2)$ time when the width is given, and in $O(ne^{\min(\operatorname{tdw}(a),\operatorname{tdw}(b))(1+o(1))})$ time otherwise, without requiring a decomposition. For Multiple-Sequence $(\min,+)$ Convolution, we give a randomized algorithm running in $O(kn^2\sqrt{\min(k,n)}\log^{1.5}(kn))$ time for $k$ sequences of length at most $n$, improving the natural $O(k^2n^2)$ bound. We also obtain conditional lower bounds, a faster single-entry algorithm, and new upper bounds for Multiple-Choice Knapsack. Finally, bounded-decomposition-width classes admit interpolation algebras of finite generating rank, whereas distinguishing all tropical polynomials of degree at most $n$ requires rank exactly $\lfloor n/2\rfloor+1$. We further show that tropical decomposition width cannot decrease under any flat $\mathbb T$-algebra extension. These results connect efficient tropical multiplication with structural rigidity.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

30 extracted references · 29 canonical work pages

  1. [1]

    Recognizing Sumsets is NP-Complete

    [AFSW25] Amir Abboud, Nick Fischer, Ron Safier, and Nathan Wallheimer. Recognizing Sumsets is NP-Complete. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2025), pages 4484–4506. SIAM,

    work page 2025

  2. [5]

    Approximating APSP without scaling: equivalence of approximate min-plus and exact min-max

    [BKW19] Karl Bringmann, Marvin Künnemann, and Karol Węgrzycki. Approximating APSP without scaling: equivalence of approximate min-plus and exact min-max. In Proceedings of the 51st Annual ACM Symposium on Theory of Computing (STOC 2019), pages 943–954. ACM,

    work page 2019

  3. [10]

    Chan and Moshe Lewenstein

    [CL15] Timothy M. Chan and Moshe Lewenstein. Clustered integer 3SUM via additive combinatorics. In Proceedings of the 47th Annual ACM Symposium on Theory of Computing (STOC 2015), pages 31–40. ACM,

    work page 2015

  4. [12]

    An Improved Pseudopolynomial Time Algorithm for Subset Sum

    50 [CLMZ24b] Lin Chen, Jiayi Lian, Yuchen Mao, and Guochuan Zhang. An Improved Pseudopolynomial Time Algorithm for Subset Sum. In Proceedings of the 65th IEEE Symposium on Foundations of Computer Science (FOCS 2024), pages 2202–2216. IEEE,

    work page 2024

  5. [15]

    Chan, Virginia Vassilevska Williams, and Yinzhan Xu

    [CWX23] Timothy M. Chan, Virginia Vassilevska Williams, and Yinzhan Xu. Fredman’s Trick Meets Dominance Product: Fine-Grained Complexity of Unweighted APSP, 3SUM Counting, and More. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC 2023), pages 419–432. ACM,

    work page 2023

  6. [16]

    In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2023), pages 2980–2990

    [DMZ23] MingyangDeng, XiaoMao, andZiqianZhong.OnProblemsRelatedtoUnboundedSubsetSum: A Unified Combinatorial Approach. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2023), pages 2980–2990. SIAM,

    work page 2023

  7. [20]

    0-1 Knapsack in Nearly Quadratic Time

    [Jin24] Ce Jin. 0-1 Knapsack in Nearly Quadratic Time. In Proceedings of the 56th Annual ACM Sym- posium on Theory of Computing (STOC 2024), pages 271–282. ACM,

    work page 2024

  8. [21]

    In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026), volume 374 of LIPIcs, pages 119:1–119:23

    51 [JPSX26] CeJin, JaewooPark, BarnaSaha, andYinzhanXu.DeterministicMonotoneMin-PlusProduct and Convolution. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026), volume 374 of LIPIcs, pages 119:1–119:23. Schloss Dagstuhl – Leibniz-Zentrum für Informatik,

    work page 2026

Show all 30 references
  1. [23]

    On the Fine-Grained Com- plexity of One-Dimensional Dynamic Programming

    [KPS17] Marvin Künnemann, Ramamohan Paturi, and Stefan Schneider. On the Fine-Grained Com- plexity of One-Dimensional Dynamic Programming. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017), volume 80 of LIPIcs, pages 21:1–21:15. Schloss Dags...

    2017

  2. [24]

    [KR05] Ki Hang Kim and Fred W. Roush. Factorization of polynomials in one variable over the tropical semiring. arXiv:math/0501167,

    arXiv

  3. [25]

    On lower bounds for the maximum consecutive subsums problem and the (min,+)-convolution

    [LRC14] Eduardo Sany Laber, Wilfredo Bardales Roncalla, and Ferdinando Cicalese. On lower bounds for the maximum consecutive subsums problem and the (min,+)-convolution. In 2014 IEEE Inter- national Symposium on Information Theory (ISIT 2014), pages 1807–1811. IEEE,

    2014

  4. [1949]

    Universe Reduction for APSP: Equivalence of Three Fine-Grained Hypotheses

    [Fis26] Nick Fischer. Universe Reduction for APSP: Equivalence of Three Fine-Grained Hypotheses. In Proceedings of the 58th Annual ACM Symposium on Theory of Computing (STOC 2026), pages 922–932. ACM,

    2026

  5. [1952]

    Better approximations for tree sparsity in nearly-linear time

    [BIS17] Arturs Backurs, Piotr Indyk, and Ludwig Schmidt. Better approximations for tree sparsity in nearly-linear time. In Proceedings of the 2017 Annual ACM-SIAM Symposium on Discrete Algo- rithms (SODA 2017), pages 2215–2229. SIAM,

    2017

  6. [1963]

    Simple and faster algorithms for knapsack

    [HX24] Qizheng He and Zhean Xu. Simple and faster algorithms for knapsack. In 2024 Symposium on Simplicity in Algorithms (SOSA 2024), pages 56–62. SIAM,

    2024

  7. [1965]

    Chan and Ryan Williams

    [CW16] Timothy M. Chan and Ryan Williams. Deterministic APSP, Orthogonal Vectors, and More: Quickly Derandomizing Razborov-Smolensky. In Proceedings of the 2016 Annual ACM-SIAM Sym- posium on Discrete Algorithms (SODA 2016), pages 1246–1255. SIAM,

    2016

  8. [1979]

    Faster all-pairs shortest paths via circuit complexity

    [Wil14] Ryan Williams. Faster all-pairs shortest paths via circuit complexity. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC 2014), pages 664–673. ACM,

    2014

  9. [1987]

    A subquadratic approximation scheme for partition

    [MWW19] Marcin Mucha, Karol Węgrzycki, and Michał Włodarczyk. A subquadratic approximation scheme for partition. In Proceedings of the 2019 Annual ACM-SIAM Symposium on Discrete Algo- rithms (SODA 2019), pages 70–88. SIAM,

    2019

  10. [1992]

    Knapsack with Small Items in Near-Quadratic Time

    [Bri24] Karl Bringmann. Knapsack with Small Items in Near-Quadratic Time. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC 2024), pages 259–270. ACM,

    2024

  11. [1998]

    Polynomials over idempotent semifields

    [Pon26] Paul Poncet. Polynomials over idempotent semifields. arXiv:2607.10492,

    arXiv

  12. [1999]

    Faster Monotone Min-Plus Product, Range Mode, and Single Source Replacement Paths

    [GPVX21] Yuzhou Gu, Adam Polak, Virginia Vassilevska Williams, and Yinzhan Xu. Faster Monotone Min-Plus Product, Range Mode, and Single Source Replacement Paths. In 48th International Col- loquium on Automata, Languages, and Programming (ICALP 2021), volume 198 of LIPIcs, page...

    2021

  13. [2014]

    Frances Yao

    [Yao80] F. Frances Yao. Efficient dynamic programming using quadrangle inequalities. In Proceedings of the 12th Annual ACM Symposium on Theory of Computing (STOC 1980), pages 429–435. ACM,

    1980

  14. [2015]

    Faster Algorithms for Bounded Knapsack and Bounded Subset Sum Via Fine-Grained Proximity Results

    [CLMZ24a] Lin Chen, Jiayi Lian, Yuchen Mao, and Guochuan Zhang. Faster Algorithms for Bounded Knapsack and Bounded Subset Sum Via Fine-Grained Proximity Results. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2024), pages 4828–4848. SIAM,

    2024

  15. [2016]

    Chan, Virginia Vassilevska Williams, and Yinzhan Xu

    [CWX22] Timothy M. Chan, Virginia Vassilevska Williams, and Yinzhan Xu. Hardness for Triangle Problems under Even More Believable Hypotheses: Reductions from Real APSP, Real 3SUM, and OV. In Proceedings of the 54th Annual ACM Symposium on Theory of Computing (STOC 2022), pages...

    2022

  16. [2017]

    In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), volume 132 of LIPIcs, pages 19:1–19:13

    [AT19] KyriakosAxiotisandChristosTzamos.Capacitateddynamicprogramming: FasterKnapsackand graph algorithms. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), volume 132 of LIPIcs, pages 19:1–19:13. Schloss Dagstuhl – Leibniz-Zentrum für Informatik,

    2019

  17. [2019]

    Fast Convolutions for Near-Convex Sequences

    [BL23] Cornelius Brand and Alexandra Lassota. Fast Convolutions for Near-Convex Sequences. In 34th International Symposium on Algorithms and Computation (ISAAC 2023), volume 283 of LIPIcs, pages 16:1–16:16. Schloss Dagstuhl – Leibniz-Zentrum für Informatik,

    2023

  18. [2021]

    Limited subsets of a free monoid

    [Sim78] Imre Simon. Limited subsets of a free monoid. In Proceedings of the 19th Annual Symposium on Foundations of Computer Science (FOCS 1978), pages 143–150. IEEE,

    1978

  19. [2022]

    Faster Min-Plus Product for Mono- tone Instances

    [CDXZ22] Shucheng Chi, Ran Duan, Tianle Xie, and Tianyi Zhang. Faster Min-Plus Product for Mono- tone Instances. In Proceedings of the 54th Annual ACM Symposium on Theory of Computing (STOC 2022), pages 1529–1542. ACM,

    2022

  20. [2023]

    Chan, Erik D

    [BCD+06] David Bremner, Timothy M. Chan, Erik D. Demaine, Jeff Erickson, Ferran Hurtado, John Iacono, Stefan Langerman, and Perouz Taslakian. Necklaces, convolutions, and x+y. In Algorithms – ESA 2006, volume 4168 of Lecture Notes in Computer Science, pages 160–171. Springer,

    2006

  21. [2024]

    Faster Algorithms for Bounded-Difference Min-Plus Product

    [CDX22] Shucheng Chi, Ran Duan, and Tianle Xie. Faster Algorithms for Bounded-Difference Min-Plus Product. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2022), pages 1435–1447. SIAM,

    2022

  22. [2026]

    On the Fine-Grained Complexity of the Unbounded SubsetSum and the Frobenius Problem

    [Kle22] Kim-Manuel Klein. On the Fine-Grained Complexity of the Unbounded SubsetSum and the Frobenius Problem. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algo- rithms (SODA 2022), pages 3567–3582. SIAM,

    2022

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.