arXiv:2610.10282v1 Announce Type: cross Abstract: 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 $\beta$-bit integer entries can be computed in $D^{3-\delta}\operatorname{poly}(\beta,\log D)$ time for a fixed rational $0<\delta<1$, then min-sum subset convolution on an $n$-element universe can be solved in $(2+2^{-\delta})^n 2^{O(\sqrt n\log(n+1))}\operatorname{poly}(n,\beta)$ 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.