Improving Schroeppel and Shamir's algorithm for subset sum via orthogonal vectors
Jesper Nederlof, Karol Wegrzycki
2021Year
8Top-tier citations
Abstract
We present an O∗(20.5n) time and O∗(20.249999n) space randomized algorithm for solving worst-case Subset Sum instances with n integers. This is the first improvement over the long-standing O∗(2n/2) time and O∗(2n/4) space algorithm due to Schroeppel and Shamir (FOCS 1979).
Ask about this paper
Your agent reads all of it.
Lune indexed this paper to the last equation, along with the top-tier papers that cite it. Ask a question and the answer quotes them.
Your agent calls
Luneget_paper_fulltext
Free to start. No credit card required.
Terminal
Install the CLIlune papers fulltext bc1d3de8-9d84-44f9-9121-89a5215d592fCited by top-tier papers8
- Fast Low-Space Algorithms for Subset SumCe Jin, Nikhil Vyas, Ryan WilliamsSODA 2021 · 10 citations
- Beating Meet-in-the-Middle for Subset Balancing ProblemsTim Randolph, Karol WegrzyckiSTOC 2026 · 5 citations
- Truly Low-Space Element Distinctness and Subset Sum via Pseudorandom Hash FunctionsLijie Chen, Ce Jin, R. Ryan Williams, Hongxun WuSODA 2022 · 3 citations
- The Orthogonal Vectors Conjecture and Non-Uniform Circuit Lower BoundsRyan WilliamsFOCS 2024 · 2 citations
- Beating Bellman's Algorithm for Subset SumKarl Bringmann, Nick Fischer, Vasileios NakosSODA 2025 · 2 citations
Builds on1
Related papers
- Derandomizing Pseudopolynomial Algorithms for Subset SumTimothy M. ChanSODA 2026
- Average-Case Subset Balancing ProblemsXi Chen, Yaonan Jin, Tim Randolph, Rocco A. ServedioSODA 2022 · 2 citations
- An Improved Pseudopolynomial Time Algorithm for Subset SumLin Chen, Jiayi Lian, Yuchen Mao, Guochuan ZhangFOCS 2024 · 5 citations
- On Near-Linear-Time Algorithms for Dense Subset SumKarl Bringmann, Philip WellnitzSODA 2021 · 19 citations
- Approximately Counting Knapsack Solutions in Subquadratic TimeWeiming Feng, Ce JinSODA 2025
