pipette
ESEspañol

Truly Sub- Min-Sum Subset Convolution and Join Ordering

Mihail Stoian

PreprintClaims a big step

In the authors' words

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 matrices with -bit integer entries can be computed in time for a fixed rational , then min-sum subset convolution on an -element universe can be solved in 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 and a deterministic algorithm with running time , strictly breaking the longstanding 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 cost function.

Main resultLimitation the authors admit

In plain words AI summary

The authors created a deterministic method that converts min-sum subset convolution problems into min-plus matrix product problems. They proved that faster min-plus matrix multiplication leads to faster min-sum subset convolution, with specific time formulas given. Using recent advances in matrix multiplication, they achieved expected time O*(2.9987^n) and deterministic time O*(2.9997^n), beating the previous 3^n limit. These same speedups apply directly to database query optimization for join ordering under the C_out cost function.

Written by Kimi K2.5 using only the abstract above. Jev checked that every sentence is supported by the abstract sentences it cites, and removed any that were not. Point at a sentence to highlight its source.

Appeared: Thursday, October 8. arXiv. Preprint, not yet peer-reviewed.

Authors' comment: Feedback welcome