Ce Jin: 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 \subseteq [n] such that \sum_{i\in S}a_i = t. The well-known pseudopolynomial-time dynamic programming algorithm [Bellman, 1957] solves Subset Sum in O(nt) time, while requiring Omega(t) space.

We present algorithms for Subset Sum with O~(nt) running time (where O~ hides polylog factors) and much lower space requirements than Bellman’s algorithm, as well as that of prior work. Our main result is a randomized algorithm for Subset Sum in O~(nt) time and O(log n loglog n + log t) space. This significantly improves upon the O~(n t^(1+eps) )-time, O~(n log t)-space algorithm of Bringmann (SODA 2017). Moreover, we show how to extend our algorithm to output a subset summing to t, with the same time complexity and space complexity. This is better than the trivial search-to-decision reduction which incurs a factor of n in the time complexity.

Based on a SODA 2021 paper joint with Nikhil Vyas and Ryan Williams, and a recent unpublished result.