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

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 }\mathrm{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))}\mathrm{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^{\ast }(2.9987^n)$ and a deterministic algorithm with running time $O^{\ast }(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.

arXiv commentFeedback welcome; v2: fixed technique naming