AG 1   Info

AG Audience

English

30 Minutes

Saarbrücken

In the classical Subset Sum 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 O~(t)-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·out), where out is the number of different subset sums of X that are smaller than t. As the aforementioned two running times are incomparable, in this paper we ask whether one can achieve the best of both worlds: running time O~(out). In particular, we ask whether the set of all subset sums smaller than t can be computed in near-linear time in the output-size. Using a diverse toolkit containing techniques such as color coding, sparse recovery, and sumset estimates, we make considerable progress towards this question and design an algorithm running in time O~(out^{4/3}).

Central to our approach is the study of top-k-convolution, a natural problem of independent interest: given sparse polynomials with non-negative coefficients, compute the lowest k non-zero monomials of their product.

Karl Bringmann

--email hidden

passcode not visible

logged in users only