Subset Sum via Partial Match
In the authors' words
We show that the subset sum problem can be solved in time , breaking the meet-in-the-middle barrier. Our approach builds on the representation technique framework of Randolph and W\k{e}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 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).
Main resultThe abstract does not state a limitation.
Appeared: Thursday, October 8. arXiv. Preprint, not yet peer-reviewed.
Authors' comment: 21 pages