On Near-Linear-Time Algorithms for Dense Subset Sum
share
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 mx_X and the sum of all input numbers Σ_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 Õ(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,mx_X,Σ_X for which dense Subset Sum is in time Õ(n). For notational convenience we assume without loss of generality that t ≥mx_X (as larger numbers can be ignored) and t ≤Σ_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 Õ(n) if t ≫mx_X Σ_X/n^2. - We prove a matching conditional lower bound: If Subset Sum is in near-linear time for any setting with t ≪mx_X Σ_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.
READ FULL TEXT