Browse › Theoretical computer science › 138 Subset Sum in $O(2^{0.49n})$ time
Subset Sum in Time $O(2^{0.49n})$
Open PDFCite Report a problem Add a reference or comment Interested in working on this Start a discussion
Edit NOTES.md · Existing issues · Source on GitHub
Abstract
We give a uniform randomized classical algorithm for Subset Sum with bounded error and worst-case running time $O(2^{0.49n})$ on polynomial-bit inputs in a word-RAM model, where n is the number of input integers. The time bound holds on every random execution.
If the PDF does not display here, open it directly: Open PDF.
Notes
No notes yet. Add a reference, a comment or your name with the buttons above, or edit NOTES.md on GitHub.
Automatically collected notes (unreviewed)
work in progress
Collected automatically by AI tools (Claude Opus 5.5 and GPT-6 Astra, 2026-10-21) and not checked by a person. May be wrong or incomplete. Report an error.
Follow-up works
- Annanay Kapila, Subset Sum in time O(2^{0.4877n}) (hexagon:2610.00261v1, 15 Oct 2026). States that it builds on this paper, keeping its framework of isolation, capped preliminary search, modular checksum and alias subtraction, replacing the alias procedure and using 43 checksum filters, and claiming exponent 0.4877; results of this paper are restated in an appendix and Arb-based scripts check numerical inequalities. [AI-generated per source]
- Joshua Wharton, A conditional refinement of the Subset Sum exponent to 0.487676 (GitHub manuscript, 20 October 2026). Refines parameters and transfers certificates from Kapila's follow-up, retaining explicit dependence on the underlying algorithmic and analytic premises. [AI-generated per source]
Formalization
- Joshua Wharton, Lean formalisation: scope and reproduction (GitHub, updated 20 October 2026). Reports compiled Lean proofs for finite certificates, numerical inequalities, isolation and supporting lemmas in the conditional refinement, while leaving continuous moment bounds as hypotheses and the complete solver's operation-count guarantee unproved. [AI-generated per source]
Possibly relevant literature (found by the agent, not checked)
- Jesus Salas, Beyond Worst-Case Subset Sum: An Adaptive, Structure-Aware Solver with Sub-$2^{n/2}$ Enumeration (arXiv:2503.20162, v1 Mar 2025, v3 Dec 2025). An earlier preprint that also claims a worst-case bound of roughly $O^*(2^{n/2-\varepsilon})$ for Subset Sum (via a technique it calls "Controlled Aliasing"), the type of statement made in Theorem 1.1; not cited in this paper.
- Marcin Mucha, Jesper Nederlof, Jakub Pawlewicz, Karol Węgrzycki, Equal-Subset-Sum Faster Than the Meet-in-the-Middle (arXiv:1905.02424, 2019). Beats the meet-in-the-middle bound in the worst case for the related Equal-Subset-Sum problem, relevant to the paper's "Related approaches" discussion of representation methods and worst-case savings.
- Yiming Gao, Yansong Feng, Honggang Hu, Yanbin Pan, Subset Balancing and Generalized Subset Sum via Lattices (arXiv:2604.04656, Apr 2026). Gives lattice-based algorithms for Subset Balancing and Generalized Subset Sum, the setting of the Randolph–Węgrzycki work that the paper contrasts with ordinary Subset Sum.
Digests and expositions
- Sankalp Thakur, Speed Limits I: Multiplying, Transforming, Factoring (Deep End Era, episode 81, undated). Includes segments on the claimed Subset Sum time improvement at 40:22 and how a referee would test it at 44:10, with disclosed AI-generated scripting and synthetic narration. [AI-generated per source]
- dimenwarper, oai-math-vids, video 30 "Subset Sum in O(2^0.49n) time (138)" (GitHub, Oct 2026). A 4:50 narrated explainer video on this family's result in an unofficial series of Manim videos on the release. [AI-generated per source] [family-level]
Elsewhere
- VibeMathed: Problem record
- Emergent Mind: family 138
Independent sites; their content is not reviewed here.
Cite
@misc{OAI:Subset-Sum-in-Time-2-power-0-49n-October-4-2026,
author = {{OpenAI}},
title = {{Subset Sum in Time $O(2^{0.49n})$}},
howpublished = {OpenAI Math Release preprint
\href{https://github.com/openai/math/blob/main/preprints/Subset-Sum-in-Time-2-power-0-49n-October-4-2026/subset-sum.pdf}{OAI:Subset-Sum-in-Time-2-power-0-49n-October-4-2026}},
year = {2026}
}Family 138: Subset Sum in $O(2^{0.49n})$ time
Gives a uniform randomized classical algorithm for worst-case Subset Sum in ordinary $O(2^{0.49n})$ word-RAM time on polynomial-bit inputs, where n counts the integers. The time bound holds on every execution and success probability is at least 2/3 on every input. Inputs may repeat positive integers; words have $O(n+b)$ bits for maximum input bit length b.
Other papers in this family:
- A Low-Space Algorithm for Worst-Case Subset Sum · September 26, 2026