cs.DS — Data Structures and Algorithms
Subset Sum in time O(2^{0.4877n})
We present a uniform randomized classical algorithm for Subset Sum with running time O(2^{0.4877n}) in the word-RAM model, for inputs whose integer bit lengths are polynomially bounded in the number n of input integers. The algorithm halts on every execution and answers correctly with probability at least 2/3. The construction builds on OpenAI’s “Subset Sum in Time O(2^{0.49n})” (4 October 2026), retaining its framework of isolation, a capped preliminary search, a modular checksum, and alias subtraction. Two components are replaced: an alias procedure that computes phase sums using a smaller modulus, and a family of 43 checksum filters selected according to the input pattern. The analysis combines an averaged small-layer lemma, grouping by reduced and unreduced subset sums, and rigorous numerical certificates. Verification scripts using Arb ball arithmetic check the alias constraints and 430 moment inequalities. The argument relies on results from the earlier paper, which are restated in an appendix; the numerical certificates verify specified inequalities rather than formally verifying the entire proof.