Subset sum problem solved faster using partial match techniques
Subset Sum via Partial Match
Data Structures and AlgorithmsComputational Complexity
Summary
The subset sum problem is about finding which numbers add up to a specific total, typically solved by splitting the problem into two halves. The authors found a way to beat the usual time barrier by linking this problem to something called partial match, which checks how partial solutions fit together. They created a new mathematical tool called a depth-2 linear circuit that helps solve the partial match problem more efficiently, which in turn speeds up solving the subset sum problem.
What this means in practice
- •For cryptographic engineers: Design faster algorithms for cryptanalysis based on subset sum hardness assumptions.
- •For optimization software developers: Improve exact subset selection modules by integrating faster subset sum algorithms to handle larger instances.
A theory result. No direct application yet.
Authors
Lixi Ye, Baitian Li
Abstract
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. Our approach builds on the representation technique framework of Randolph and Węgrzycki (STOC 2026). We choose a representation for which testing the compatibility of pairs of partial solution vectors is exactly the partial match problem. To beat exponent $1/2$ for subset sum, it then suffices to give a nontrivial partial match algorithm in a certain parameter regime. We achieve this by designing a depth-2 linear circuit for the partial match matrix, which yields an efficient algorithm via the framework of Alman and Li (FOCS 2025).