Top-𝑘-convolution and the quest for near-linear output-sensitive subset sum

Abstract

In the classical SubsetSum problem we are given a set X and a target t, and the task is to decide whether there exists a subset of X which sums to t. A recent line of research has resulted in (t · poly (logt))-time algorithms, which are (near-)optimal under popular complexity-theoretic assumptions. On the other hand, the standard dynamic programming algorithm runs in time O(n · |S(X,t)|), where S(X,t) is the set of all subset sums of X that are smaller than t. All previous pseudopolynomial algorithms actually solve a stronger task, since they actually compute the whole set S(X,t).