Fast Low-Space Algorithms for Subset Sum

We consider the canonical Subset Sum problem: given a list of positive integers a 1 , . . . , a n and a target integer t with t > a i for all i, determine if there is an S ⊆ [n] such that i∈S a i = t. The wellknown pseudopolynomial-time dynamic programming algorithm [Bellman, 1957] solves Subset Sum in O(nt) time, while requiring Ω(t) space.

In this paper we present algorithms for Subset Sum with O(nt) running time and much lower space requirements than Bellman's algorithm, as well as that of prior work. We show that Subset Sum can be solved in O(nt) time and O(log(nt)) space with access to O(log n log log n + log t) random bits. This significantly improves upon the O(nt 1+ε )-time, O(n log t)-space algorithm of Bringmann (SODA 2017). We also give an O(n 1+ε t)-time, O(log(nt))-space randomized algorithm, improving upon previous (nt) O(1) -time O(log(nt))-space algorithms by Elberfeld, Jakoby, and Tantau (FOCS 2010), and Kane (2010). In addition, we also give a poly log(nt)-space, O(n 2 t)-time deterministic algorithm.

We also study time-space trade-offs for Subset Sum. For parameter 1 ≤ k ≤ minn, t, we present a randomized algorithm running in O((n + t) • k) time and O((t/k) poly log(nt)) space.

As an application of our results, we give an O(minn 2 /ε, n/ε 2 )-time and poly log(nt)-space algorithm for "weak" ε-approximations of Subset Sum.