arXiv preprint ·
Pigeonhole Equal Subset Sum: Subexponential Algorithm, Tight Lower Bounds, and Average-Case Analysis
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Optimal Mixing for Local Edge-Coloring Dynamics on Trees
Beyond 3SUM-Hardness for Geometric Problems
Report the tolerance, not the count: exact phylogenetic distance deconvolution with incomplete references
The Exact Robustness of Smith's Rule with Predicted Processing Times
Near-Quadratic Time Multivariate Polynomial Interpolation
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.