Abstract

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 a subset S of [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.

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 loglog n+log t) random bits. This significantly improves upon the ~O(n t^{1+eps})-time, ~O(n log t)-space algorithm of Bringmann (SODA 2017). We also give a ~O(n^{1+eps}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).

Joint work with Nikhil Vyas and Ryan Williams.

Biography

Ce Jin is a final-year undergraduate in Yao Class, Tsinghua University. He is interested in algorithm design and computational complexity.

Admission: https://www.wjx.cn/m/83029003.aspx
Online Talk:  https://zoom.com.cn/j/99141724412