arXiv:2610.10446 · v2

Subset Sum via Partial Match

首次提交 2026-10-08 01:18

版本更新 2026-11-03 02:29

雷达观测 2026-11-04 23:41

摘要

We show that the subset sum problem can be solved in randomized time $O(2^{0.49999\overline{7}n})$, 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).

作者备注：33 pages, 1 figure