Subset Sum in Near-Linear Pseudopolynomial Time and Polynomial Space

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^{2}t)$ time and $\tilde{O}(n{\log }^{2}t)$ space.