Algorithms improve finding equal sum subsets among numbers
Pigeonhole Equal Subset Sum: Subexponential Algorithm, Tight Lower Bounds, and Average-Case Analysis
Data Structures and Algorithms
Summary
The Equal Subset Sum problem asks if we can find two different groups of numbers from a list that add up to the same total. The authors improve the speed of algorithms that solve this problem when the numbers are not too large, making it easier to find these groups efficiently. They also show that getting much faster algorithms would be very hard without breakthroughs in related math areas. Additionally, they created an even faster method for typical cases when the numbers are very large.
What this means in practice
- •For cryptography engineers: Evaluate security limits by understanding algorithmic hardness linked to lattice problems relevant in cryptography.
- •For algorithm developers: Use improved subexponential algorithms to speed up subset sum computations in combinatorial optimization tasks.
Authors
Deepak Bhati, Pranjal Dutta, Antoine Joux, Mahesh Sreekumar Rajasree, Karol Wegrzycki
Abstract
The Equal Subset Sum problem asks, given n positive integers bounded by M, to find two distinct non-empty subsets with the same sum. We study this problem in the regime $M = 2^{o(n)}$, where the pigeonhole principle guarantees that a solution exists, and the main challenge is to find one efficiently. A straightforward dynamic-programming algorithm runs in time poly(n).$M$. After a sequence of improvements, the current best algorithm, due to Jin, Williams, and Zhang (ESA 2025), achieves running time poly(n).$M^{1/3}$. In this work, we give the first poly(n).$M^{o(1)}$-time algorithm for Equal Subset Sum in the regime $M = 2^{o(n)}$. We complement this algorithmic result with a tight conditional lower bound showing that any substantial improvement would require a major breakthrough in approximation algorithms for lattice problems, building on recent techniques of Vafa and Vaikuntanathan (STOC 2025). Finally, we show that our techniques yield an asymptotically faster algorithm for the regime when $M = Θ(2^{n})$: a poly(n)$\cdot 2^{n/4}$-time algorithm in the average case.