Jennifer Voitle

cs.DS — Data Structures and Algorithms

A certified exponent of 0.48758 for worst-case Subset Sum, and limits of the alias–checksum analysis

Contributed by Jennifer Voitle

For more than fifty years, since Horowitz and Sahni's meet-in-the-middle algorithm of 1974, the best exponent for worst-case Subset Sum was $1/2$. In October 2026 that barrier fell twice within a week, with OpenAI's $2^{0.49n}$ algorithm and, independently, Li and Ye's $2^{(1/2 - 1/450000)n} \approx 2^{0.4999978n}$, and improvements have followed quickly since: within three weeks A. Kapila's modification of the OpenAI approach ("Base") reached 0.4877, a retuning of Base by JoshuaQFEX reached 0.487676, and a refinement by Y. Bills reached 0.4876723. Here we push this line of work further and examine what limits it. Conditional on the cited non-numerical proofs, we give a certified parameter point with threshold $T=0.4875754036$: for every fixed $T'>T$, the uniform randomized algorithm uses $O(2^{T'n})$ word operations on inputs of polynomial bit length, with success probability at least $2/3$. In particular, it runs in time $O(2^{0.4875755n})$. A single asymmetric filter replaces Base's family of 43 filters. Independent interval computations certify all required numerical conditions, including both filtering moments and their quadrature errors. We prove a lower bound on the first filtering moment, valid for all positive continuous densities, that excludes every parameter choice with $\tau\le0.484$ in the original OpenAI proof's sufficient budget. Three algebraic bounds explain the costs at our improved point. Separately, an enumeration phase that inserts at least $2^{(1-\eta-o(1))n}$ alias classes, spending a counted step on each, and uses checksum gap at most $\Delta$ needs exponent at least $(1-\Delta)/2$. This is a conditional operation-count bound; a global upper bound on achievable checksum capacity remains open. Finally, we isolate a small-layer statement that would yield threshold $0.4873407528$, prove combinatorial special cases, and identify the remaining questions.

Author comments: 30 pages, 2 figures. The main result is conditional on the written proofs of OpenAI (4 Oct 2026) and A. Kapila (commit 44c34961); its numerical conditions are certified in interval arithmetic. The companion file SECTION_T_v3.pdf (full proofs of the ternary alias step, Appendix A) is included with the source. Code, certificates, verification scripts and a timestamped research record: https://github.com/jv1000/subset-sum. AI use is described in Section 11.