PaperfootJoin free
arXiv

An algorithm breaks a time barrier for the subset sum problem

A preprint proves that the subset sum problem can be solved faster than the meet-in-the-middle barrier by using a partial match algorithm.

Paper by Lixi Ye, Baitian Li
A light blue lattice holds a black path to a fitted square, beside scattered gray pieces and separated dark blue-green comb shapes.
Preprint: theory

Edited by Boris Djordjevic · Paperfoot

Paper

This theory preprint proved that the subset sum problem can be solved in time O(2^(0.499999n)). This result broke the 2^(n/2) meet-in-the-middle barrier. The approach built on the representation technique framework of Randolph and Węgrzycki. The authors chose a representation where testing the compatibility of pairs of partial solution vectors is exactly the partial match problem.

To beat exponent 1/2 for subset sum, giving a nontrivial partial match algorithm in a certain parameter regime was sufficient. The authors achieved this by designing a depth-2 linear circuit for the partial match matrix. This circuit yielded an efficient algorithm through the framework of Alman and Li.

Why it matters

The proof settles an open question in theoretical computer science by showing that the subset sum problem can be solved faster than the meet-in-the-middle barrier. The evidence is a mathematical proof that establishes a theoretical speedup by connecting subset sum to partial match algorithms and linear circuits.

Caveats

The result is a theoretical proof rather than an empirical evaluation on real computing hardware. The paper is also a preprint that has not yet undergone formal peer review.

In this paper

subset sum problem

What it shows

The subset sum problem can be solved in time O(2^(0.499999n)), breaking the 2^(n/2) meet-in-the-middle barrier.

We show that the subset sum problem can be solved in time O(2^(0.499999n)), breaking the 2^(n/2) meet-in-the-middle barrier.

Abstract

Every exponent pair in K(1/2) is an admissible exponent pair.

Every pair in \mathcal{K}\left(\frac{1}{2}\right) is an admissible exponent pair.

Corollary 3.3.

The optimal PAR and OR value of (delta_L + delta_R)/2 is (h(s) - s)/2 for s <= 1/2, and (1 - s)/2 otherwise, attained by b = min(2s, 1).

Consequently, the optimal \mathsf{PAR} and \mathsf{OR} value of \frac{\delta_{\mathsf{L}}+\delta_{\mathsf{R}}}{2} is \frac{\mathrm{h}(s)-s}{2} for s≤\frac{1}{2}, and \frac{1-s}{2} otherwise, attained by b=\min(2s,1).

3.2 The Fredman–Volper circuit

Quoted word for word from the full text on arXiv.

The paper

Subset Sum via Partial Match

Lixi Ye, Baitian Li

arXiv, Oct 7, 2026, Open access, Preprint, not peer-reviewed

doi.org/10.48550/arxiv.2610.10446

arXiv:2610.10446v1 in cs.DS, also cs.CC

AbstractPDFHTML

Comments: 21 pages

Cite as BibTeX
@misc{ye2026subset,
  title = {Subset Sum via Partial Match},
  author = {Ye, Lixi and Li, Baitian},
  year = {2026},
  eprint = {2610.10446},
  archivePrefix = {arXiv},
  primaryClass = {cs.DS},
  doi = {10.48550/arxiv.2610.10446},
  url = {https://arxiv.org/abs/2610.10446}
}

Related