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

Mihail Stoian

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 integ…