{"ID":2886527,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2508.04726","arxiv_id":"2508.04726","title":"Subset Sum in Near-Linear Pseudopolynomial Time and Polynomial Space","abstract":"Given a multiset $A = \\{a_1, \\dots, a_n\\}$ of positive integers and a target integer $t$, the Subset Sum problem asks if there is a subset of $A$ that sums to $t$. Bellman's [1957] classical dynamic programming algorithm runs in $O(nt)$ time and $O(t)$ space. Since then, much work has been done to reduce both the time and space usage. Notably, Bringmann [SODA 2017] uses a two-step color-coding technique to obtain a randomized algorithm that runs in $\\tilde{O}(n+t)$ time and $\\tilde{O}(t)$ space. Jin, Vyas and Williams [SODA 2021] build upon the algorithm given by Bringmann, using a clever algebraic trick first seen in Kane's Logspace algorithm, to obtain an $\\tilde{O}(nt)$ time and $\\tilde{O}(\\log(nt))$ space randomized algorithm. A SETH-based lower-bound established by Abboud et al. [SODA 2019] shows that Bringmann's algorithm is likely to have near-optimal time complexity. We build on the techniques used by Jin et al. to obtain a randomized algorithm running in $\\tilde{O}(n+t)$ time and $\\tilde{O}(n^2 + n \\log^2 t)$ space, resulting in an algorithm with near-optimal runtime that also runs in polynomial space. We use a multipoint evaluation-based approach to speed up a bottleneck step in their algorithm. We also provide a simple polynomial space deterministic algorithm that runs in $\\tilde{O}(n^2t)$ time and $\\tilde{O}(n \\log^2 t)$ space.","short_abstract":"Given a multiset $A = \\{a_1, \\dots, a_n\\}$ of positive integers and a target integer $t$, the Subset Sum problem asks if there is a subset of $A$ that sums to $t$. Bellman's [1957] classical dynamic programming algorithm runs in $O(nt)$ time and $O(t)$ space. Since then, much work has been done to reduce both the time...","url_abs":"https://arxiv.org/abs/2508.04726","url_pdf":"https://arxiv.org/pdf/2508.04726v3","authors":"[\"Thejas Radhika Sajith\"]","published":"2025-08-05T18:04:36Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.CC\"]","methods":"[\"Large Language Model\"]","has_code":false}