CS Paper Radar

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

Huanyi Zhou

cs.CC cs.DM ·submitted 2026-08-13 14:37 UTC · v2
theory

Abstract

The $(\min,+)$ convolution is a central problem in fine-grained complexity, and it remains open whether it can be computed in truly subquadratic time. We study it through tropical polynomials, where $(\min,+)$ convolution is exactly tropical polynomial multiplication. We introduce the tropical decomposition width, $\operatorname{tdw}(A)$, which measures how finely a tropical polynomial can be decomposed into factors of small degree. We prove two modular convexity theorems showing that bounded tropical decomposition width forces convexity on arithmetic progression subpolynomials. This yields deterministic algorithms for computing $a\otimes b$ in $$O\left(n\max(\operatorname{tdw}(a),\operatorname{tdw}(b))^2\right)$$ when $\max(\operatorname{tdw}(a),\operatorname{tdw}(b))$ is given, and in $$O\left(ne^{\min(\operatorname{tdw}(a),\operatorname{tdw}(b))(1+o(1))}\right)$$ without prior knowledge of the width. Neither algorithm requires a decomposition of the input sequences. The same structural ideas give a randomized algorithm for Multiple-Sequence $(\min,+)$ Convolution: given $k$ sequences of length at most $n$, their convolution can be computed in $$O\left(kn^2\sqrt{\min(k,n)}\log^{1.5}(kn)\right)$$ time, improving the natural $O(k^2n^2)$ bound. Finally, we introduce interpolation algebras for tropical polynomials and show that classes with bounded tropical decomposition width admit interpolation algebras of finite generating rank, whereas distinguishing all tropical polynomials of degree at most $n$ requires generating rank $\lfloor n/2\rfloor+1$. We also prove that tropical decomposition width cannot decrease under any flat $\mathbb T$-algebra extension. Together, these results connect the tractability of $(\min,+)$ convolution with structural rigidity in tropical polynomial multiplication.

Comment
63 pages, 1 figure, abstract shortened to meet arXiv requirements

Closest papers

Nearest neighbours by meaning across the whole index.

A Note on Truly Subquadratic Time FPTAS for Knapsack

cs.DS ·2026-11-17 ·Lin Chen, Jiayi Lian, Yuchen Mao, Guochuan Zhang
similarity 0.63
Abstract

We show that an $\widetilde{O}(m^ρ)$-time algorithm for integer $(\min,+)$-convolution, where $1<ρ<2$, gives a randomized fully polynomial-time approximation scheme for $0$--$1$ Knapsack running in $\widetilde{O}(n+(1/ε)^{1+ρ/2})$ time. The algorithm returns a feasible solution whose profit is at least the optimum divided by $1+ε$, with high probability. We use the all-capacities proximity decomposition of Chen, Lian, Mao, and Zhang. Its two quadratic computations are replaced by blocked computation of requested prefix and suffix functions, and exact computation within groups sharing one of Chan's profit grids. Thus the approximation scheme retains half of the saving in the convolution exponent. Wang's weighted-cache 3SUM bound, transferred to witnessed integer convolution by Zhou, gives the numerical bound $\widetilde{O}(n+(1/ε)^{1.981})$.

0.26

Truly Sub-$3^n$ Min-Sum Subset Convolution and Join Ordering

cs.DS cs.DB ·2026-10-07 ·Mihail Stoian
hot direction similarity 0.63
Abstract · Feedback welcome; v2: fixed technique naming

We present a deterministic reduction from min-sum subset convolution to min-plus matrix product. We show that if the min-plus product of two $D\times D$ matrices with $β$-bit integer entries can be computed in $D^{3-δ}\operatorname{poly}(β,\log D)$ time for a fixed rational $0<δ<1$, then min-sum subset convolution on an $n$-element universe can be solved in $(2+2^{-δ})^n 2^{O(\sqrt n\log(n+1))}\operatorname{poly}(n,β)$ time. Instantiating this reduction with the recent breakthrough on subcubic min-plus matrix product by Alman and Vassilevska Williams gives a Las Vegas algorithm with expected running time $O^*(2.9987^n)$ and a deterministic algorithm with running time $O^*(2.9997^n)$, strictly breaking the longstanding $3^n$ computational barrier. Notably, these speedups translate directly to database query optimization, yielding the same expected and deterministic running-time bounds for join ordering under the $C_{\mathrm{out}}$ cost function.

0.27

Even Faster Algorithms for Bounded Integer Programming

cs.DS ·2026-11-18 ·Lin Chen, Yuchen Mao, Guochuan Zhang
similarity 0.61
Abstract

We study integer programs $\min\{\mathbf{c}^{T}\mathbf{x}: A\mathbf{x}=\mathbf{b},\mathbf{l}\le\mathbf{x}\le\mathbf{u},\mathbf{x}\in\mathbb{Z}^n\}$ with a fixed number $d$ of equality constraints and constraint coefficients of absolute value at most $N$. Chen, Mao, and Zhang recently solved such programs in almost $N^{2d}$ time. We show that any polynomial saving for $(\min,+)$-convolution carries over to this problem. If witnessed $(\min,+)$-convolution of arrays of length $m$ can be computed in $\tilde{O}(m^ρ)$ time with error probability $p$, then for every $\varepsilon>0$ bounded integer programming can be solved in $\tilde{O}\bigl(n+N^{(\max\{ρ,3/2\}+\varepsilon)d}\bigr)$ time with the same error probability $p$, up to polynomial factors in the encoding length and the cost of one linear program. A deterministic convolution algorithm yields a deterministic integer programming algorithm. Combined with recent truly subquadratic algorithms for $(\min,+)$-convolution, this gives a deterministic algorithm running in $\tilde{O}(n+N^{1.99986\,d})$ time and a randomized algorithm running in $\tilde{O}(n+N^{1.9602\,d})$ time, up to the same factors.

0.09

Bounding and Approximating Kostka Numbers

cs.DS math.CO ·2026-11-10 ·Jonathan Leake, Zirou Zhang
similarity 0.58
Abstract

Kostka numbers, the coefficients of Schur polynomials, count semistandard Young tableaux of prescribed shape and weight. We give a deterministic algorithm for approximating Kostka numbers within a simply exponential factor in the number of variables and the size of the partition. Our approach combines Gurvits capacity bounds for log-concave polynomials with an algorithm for approximating the Gurvits capacity of a Schur polynomial. For a Schur polynomial in $n$ variables indexed by $λ$, we show that the logarithm of the capacity associated with any nonzero coefficient can be approximated to additive error $ε$ in time polynomial in $n$, $|λ|$, and $\log(1/ε)$. The analysis establishes an explicit bounded optimization region and efficient approximate first-order oracles, and handles boundary weights through a factorization into smaller Schur polynomials.

0.21

Subexponential Approximation of the Permanent in Deterministic Polynomial Time

cs.DS cs.CCmath.CO ·2026-09-09 ·Sergei Kudria, Jason Luo, Mahbod Majid
theory similarity 0.57
Abstract · 44 pages

We give the first deterministic polynomial time algorithm that approximates the permanent of arbitrary nonnegative rational matrices within a subexponential factor. For a matrix of order $n$, the approximation factor is \[ \exp\!\left(O\!\left(\frac{n(\log\log n)^2}{\log n}\right)\right)=\exp(o(n)). \] All previously known deterministic polynomial time guarantees for unrestricted inputs had approximation factors $\exp(Ω(n))$. Our proof uses convex optimization to tighten an upper bound on the permanent. The bound is based on weighted sums over all matchings in a bipartite graph representing the matrix, and correlations between unmatched vertices control its error. We approximate these sums deterministically using correlation decay and a bound on the effect of vertex deletion.

0.45

Min-Plus Convolution Lower Bounds via a Higher-Order BSG Theorem

cs.DS ·2026-10-07 ·Nick Fischer, Ce Jin, Yinzhan Xu
top venuetheory similarity 0.57
Abstract · Appears at FOCS '26

Min-Plus Convolution is a central problem in fine-grained complexity, and the associated Min-Plus Convolution Hypothesis forms the basis for a wide range of conditional lower bounds for fundamental problems. It is closely connected to the APSP and 3SUM Hypotheses, and in fact implies both, making it a unifying hypothesis for two of the main pillars of the area. In this work we establish several strong results related to Min-Plus Convolution. We design a universe reduction, showing, under a plausible additive combinatorics assumption, that the Min-Plus Convolution Hypothesis is equivalent to the Strong Min-Plus Convolution Hypothesis. We also obtain tight conditional lower bounds for multiple long-standing problems, including Min-Max Convolution and Bounded Monotone Min-Plus Convolution. Our approach is inspired by Fischer's recent equivalence between several variants of APSP [STOC '26], but extending that technique to the arithmetic setting requires overcoming deep obstacles. To this end, we develop a novel additive structure theorem that can be viewed as a higher-order substitute of the Balog-Szemerédi-Gowers (BSG) theorem, allowing us to extract strong additive structure even from weakly structured sets. Building on this structural result, we show that certain structured 3SUM instances (namely, sets with low rank) can be solved in truly subquadratic time. This algorithm forms the main algorithmic ingredient in our reductions. Besides, it generalizes all previously known truly subquadratic-time special cases of 3SUM, and is therefore of independent interest.

0.50

Faster Stable Numerical Polynomial Multiplication

cs.DS ·2026-09-30 ·Hong Duc Bui
similarity 0.57
Abstract · 29 pages, 7 figures

In the preprint [vdH08], van der Hoeven considers the problem of multiplying two polynomials with floating-point coefficients, and give an algorithm to compute the product with small relative Newton error in time $O(np \log(np))$, where $n$ is the degree and $p$ is the required precision. In this paper, we describe a significantly simpler algorithm with the same time complexity and error bound. Independently, Bringmann and Cassis considered the near-convex min-plus convolution problem in [BC23a], and presented an algorithm to solve that problem. We observe that our algorithm can be adapted to that problem to speed up Bringmann and Cassis' algorithm by a logarithmic factor.

0.30

A Fast Algorithm for Subspace Convolution

cs.DS cs.CC ·2026-11-09 ·Shlomo A. Perles, Omri Weinstein
theorycode/data similarity 0.56
Abstract · 35 pages, 2 figures. Code, experiments, and Lean 4 formalizations: https://github.com/shlomi-perles/subspace-convolution

A cornerstone result in Boolean lattice theory is the subset-zeta transform, which computes the $f$-weighted subset summation problem $(Z f)(B)=\sum_{A\subseteq B}f(A)$ for all $ B\subseteq[n]$ in $O(N \log N)$ additions instead of the naïve $O(3^n) = O(N^{\log_2 3})$, where $N=2^n$. This paper studies the algebraic analogue of this problem--the subspace summation problem--where subsets are replaced by linear subspaces in $\mathbb{F}_q^n$. Surprisingly, we show that this problem admits a similar $Θ_q(N_q \log N_q)$-time algorithm, where $N_q$ is the number of subspaces. This improves substantially (in both theory and practice) over lattice-based algorithms ([BHK+16, KKW16]), which are known to be optimal for addition-only algorithms over $\mathbb R$. We prove similar runtimes for inversion, rank-constrained sums and span convolution. We describe two main applications: Fast linear algebra on Grassmann graphs: Matrix--vector multiplication for arbitrary distance-invariant kernels on $N$-vertex Grassmann graphs in $O_q(N\log N)$ arithmetic operations, together with fast spectral projections and exact solutions of the corresponding linear systems. Graph coloring of low binary cut-rank graphs: An $n^{2^{r^2/4+O(1)}}$-time algorithm for computing the chromatic number and chromatic polynomial of an $n$-vertex graph, given a rank-decomposition of width $r$. We also give quantitative reductions from satisfiability and monotone constraint problems. Experiments show speedups in measured running time of up to $18$ over the covering-pair algorithm for the zeta transform, $190$ over Poisson summation for rank-constrained sums, and $22$ over the distance-matrix recurrence for Grassmann kernel multiplication. Lean 4 formalizations of the transform identities, arithmetic operation bounds, and graph-coloring constructions accompany the paper [PW26].

0.28