Browse › Theoretical computer science › 138 Subset Sum in $O(2^{0.49n})$ time
A Low-Space Algorithm for Worst-Case Subset Sum
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 classical randomized decision algorithm for worst-case Subset Sum. Under every fixed polynomial bound on input-integer bit length, it uses $\mathop{\mathrm{poly}}\nolimits (n)2^{n/2}$ time and ordinary $O(2^{n/5})$ writable words of $O(n+b)$ bits, where b is the largest input bit length. Both resource bounds hold on every execution. The error is one-sided: the algorithm always rejects unsolvable instances and accepts each solvable instance with probability at least 2/3.
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.
Possibly relevant literature (found by the agent, not checked)
- Ce Jin, Nikhil Vyas and Ryan Williams, Fast Low-Space Algorithms for Subset Sum (arXiv:2011.03819, 7 November 2020; SODA 2021). Provides a comparison for the manuscript's memory-reduction claim through logarithmic-space and time–space tradeoff algorithms whose running times depend pseudopolynomially on the numerical target, rather than the manuscript's half-exponential bound in the number of integers.
- Nikhil Bansal, Shashwat Garg, Jesper Nederlof, Nikhil Vyas, Faster Space-Efficient Algorithms for Subset Sum, k-Sum and Related Problems (arXiv:1612.02788, 2016/2017). Gives polynomial-space Monte Carlo Subset Sum algorithms in about $O^*(2^{0.86n})$ time assuming random read-only access to random bits, the kind of resource the paper's model explicitly charges for ("no random oracle"); not cited in this paper.
Digests and expositions
- 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 family 138 in an unofficial series of Manim videos on the release; the listing does not say whether it covers the low-space companion paper. [AI-generated per source] [family-level]
Elsewhere
- Emergent Mind: family 138
Independent sites; their content is not reviewed here.
Cite
@misc{OAI:A-Low-Space-Algorithm-for-Worst-Case-Subset-Sum-September-26-2026,
author = {{OpenAI}},
title = {{A Low-Space Algorithm for Worst-Case Subset Sum}},
howpublished = {OpenAI Math Release preprint
\href{https://github.com/openai/math/blob/main/preprints/A-Low-Space-Algorithm-for-Worst-Case-Subset-Sum-September-26-2026/paper.pdf}{OAI:A-Low-Space-Algorithm-for-Worst-Case-Subset-Sum-September-26-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:
- Subset Sum in Time $O(2^{0.49n})$ · October 4, 2026