New algorithms break a longstanding barrier for subset problems
A preprint proved that a fundamental subset problem can be solved faster than a longstanding limit, translating directly to database query optimization.
Edited by Boris Djordjevic · Paperfoot
In a preprint presenting a theory result, researchers proved a deterministic reduction from min-sum subset convolution on an n-element universe to min-plus matrix product. A reduction is a mathematical method that transforms one problem into another. The proof showed that faster matrix multiplication directly speeds up subset calculations.
Applying this reduction to an earlier technique by Alman and Vassilevska Williams yielded two algorithms. One is a Las Vegas algorithm—a randomized method that always gives the correct answer—with an expected running time of O*(2.9987ⁿ). The second is a deterministic algorithm running in O*(2.9997ⁿ). Both strictly broke the longstanding 3ⁿ computational barrier. These speedups translated directly to database query optimization, yielding the same running-time bounds for join ordering under the Cout cost function.
Why it matters
By mathematical proof, the result settles a longstanding open problem by showing that subset convolution can beat its classic exponential barrier. It gives database engineers faster theoretical guarantees for join ordering, a core step in query optimization.
Caveats
The results are mathematical proofs rather than measured implementations on real database software, and the abstract does not report practical runtimes. The work is also a preprint that has not yet undergone peer review.
In this paper
min-sum subset convolution and join ordering
- Methods
- LeDP (this paper)DPconv (baseline)ChatGPT-6 Astra
- Links
- Code
Results
- LeDP, expected running time, Las Vegas algorithm: O^(*)(2.9987n); LeDP, running time, deterministic algorithm: O^(*)(2.9997n)
… gives a Las Vegas algorithm with expected running time O^(*)(2.9987n) and a deterministic algorithm with running time O^(*)(2.9997n), strictly breaking the longstanding 3n computational barrier …
Abstract
- LeDP, min-plus exponent, Las Vegas algorithm: 2.998; LeDP, min-plus exponent, deterministic algorithm: 2.9995
Our Lemma 8 (Appendix A) gives min-plus exponents 2.998 and 2.9995 for the Las Vegas and deterministic algorithms, respectively.
Corollary 3.
What it shows
- Min-sum subset convolution on integer inputs can be computed by a Las Vegas algorithm in expected O*(2.9987^n) time and by a deterministic algorithm in O*(2.9997^n) time.
Min-sum subset convolution on integer inputs can be computed by a Las Vegas algorithm in expected O^{*}(2.9987^{n}) time and by a deterministic algorithm in O^{*}(2.9997^{n}) time.
Corollary 2.
- The same bounds hold for join ordering under Cout whether cross products are permitted or forbidden for ordinary undirected query graphs, provided cardinality estimates can be obtained in polynomial time.
For ordinary undirected query graphs, both bounds hold whether cross products are permitted or forbidden.
Corollary 3.
- If min-plus product of two D x D integer matrices with beta-bit entries can be computed in subcubic time, min-sum subset convolution can be solved deterministically.
We show that if the min-plus product of two D× D matrices with β-bit integer entries can be computed in D^(3-δ)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(√ nlog(n+1)))poly(n,β) time.
Abstract
- For every r >= 1, a complete family of restrictions satisfying the covering bound can be deterministically constructed in 2^O(r) bit operations.
For every r≥ 1, one can deterministically construct in 2^{O(r)} bit operations a complete family \mathcal{F}_{r} satisfying
Lemma 7 (Complete local covers).
Quoted word for word from the full text on arXiv.
The paper
Truly Sub-3ⁿ Min-Sum Subset Convolution and Join Ordering
arXiv, Oct 7, 2026, Open access, Preprint, not peer-reviewed
doi.org/10.48550/arxiv.2610.10282
arXiv:2610.10282v2 in cs.DS, also cs.DB
Comments: Feedback welcome; v2: fixed technique naming
Cite as BibTeX
@misc{stoian2026truly,
title = {Truly Sub-$3^n$ Min-Sum Subset Convolution and Join Ordering},
author = {Stoian, Mihail},
year = {2026},
eprint = {2610.10282},
archivePrefix = {arXiv},
primaryClass = {cs.DS},
doi = {10.48550/arxiv.2610.10282},
url = {https://arxiv.org/abs/2610.10282}
}
