  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.
