# Item

ITEM ACTIONSEXPORT

Released

Paper

#### Top-k-Convolution and the Quest for Near-Linear Output-Sensitive Subset Sum

##### External Resource

No external resources are shared

##### Fulltext (restricted access)

There are currently no full texts shared for your IP range.

##### Fulltext (public)

arXiv:2107.13206.pdf

(Preprint), 513KB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Bringmann, K., & Nakos, V. (2021). Top-k-Convolution and the Quest for Near-Linear Output-Sensitive Subset Sum. Retrieved from https://arxiv.org/abs/2107.13206.

Cite as: https://hdl.handle.net/21.11116/0000-0009-B434-1

##### Abstract

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 $\tilde{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 \cdot

|\mathcal{S}(X,t)|)$, where $\mathcal{S}(X,t)$ is the set of all subset sums of

$X$ that are smaller than $t$. Furthermore, all known pseudopolynomial

algorithms actually solve a stronger task, since they actually compute the

whole set $\mathcal{S}(X,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

$\tilde{O}(|\mathcal{S}(X,t)|)$. In particular, we ask whether

$\mathcal{S}(X,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

$\tilde{O}(|\mathcal{S}(X,t)|^{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. We

design an algorithm running in time $\tilde{O}(k^{4/3})$, by a combination of

sparse convolution and sumset estimates considered in Additive Combinatorics.

Moreover, we provide evidence that going beyond some of the barriers we have

faced requires either an algorithmic breakthrough or possibly new techniques

from Additive Combinatorics on how to pass from information on restricted

sumsets to information on unrestricted sumsets.

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 $\tilde{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 \cdot

|\mathcal{S}(X,t)|)$, where $\mathcal{S}(X,t)$ is the set of all subset sums of

$X$ that are smaller than $t$. Furthermore, all known pseudopolynomial

algorithms actually solve a stronger task, since they actually compute the

whole set $\mathcal{S}(X,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

$\tilde{O}(|\mathcal{S}(X,t)|)$. In particular, we ask whether

$\mathcal{S}(X,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

$\tilde{O}(|\mathcal{S}(X,t)|^{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. We

design an algorithm running in time $\tilde{O}(k^{4/3})$, by a combination of

sparse convolution and sumset estimates considered in Additive Combinatorics.

Moreover, we provide evidence that going beyond some of the barriers we have

faced requires either an algorithmic breakthrough or possibly new techniques

from Additive Combinatorics on how to pass from information on restricted

sumsets to information on unrestricted sumsets.