# Item

ITEM ACTIONSEXPORT

Released

Paper

#### On Near-Linear-Time Algorithms for Dense Subset Sum

##### External Ressource

No external resources are shared

##### Fulltext (public)

arXiv:2010.09096.pdf

(Preprint), 843KB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Bringmann, K., & Wellnitz, P. (2020). On Near-Linear-Time Algorithms for Dense Subset Sum. Retrieved from https://arxiv.org/abs/2010.09096.

Cite as: http://hdl.handle.net/21.11116/0000-0007-8C97-1

##### Abstract

In the Subset Sum problem we are given a set of $n$ positive integers $X$ and
a target $t$ and are asked whether some subset of $X$ sums to $t$. Natural
parameters for this problem that have been studied in the literature are $n$
and $t$ as well as the maximum input number $\rm{mx}_X$ and the sum of all
input numbers $\Sigma_X$. In this paper we study the dense case of Subset Sum,
where all these parameters are polynomial in $n$. In this regime, standard
pseudo-polynomial algorithms solve Subset Sum in polynomial time $n^{O(1)}$.
Our main question is: When can dense Subset Sum be solved in near-linear time
$\tilde{O}(n)$? We provide an essentially complete dichotomy by designing
improved algorithms and proving conditional lower bounds, thereby determining
essentially all settings of the parameters $n,t,\rm{mx}_X,\Sigma_X$ for which
dense Subset Sum is in time $\tilde{O}(n)$. For notational convenience we
assume without loss of generality that $t \ge \rm{mx}_X$ (as larger numbers can
be ignored) and $t \le \Sigma_X/2$ (using symmetry). Then our dichotomy reads
as follows:
- By reviving and improving an additive-combinatorics-based approach by Galil
and Margalit [SICOMP'91], we show that Subset Sum is in near-linear time
$\tilde{O}(n)$ if $t \gg \rm{mx}_X \Sigma_X/n^2$.
- We prove a matching conditional lower bound: If Subset Sum is in
near-linear time for any setting with $t \ll \rm{mx}_X \Sigma_X/n^2$, then the
Strong Exponential Time Hypothesis and the Strong k-Sum Hypothesis fail.
We also generalize our algorithm from sets to multi-sets, albeit with
non-matching upper and lower bounds.