Average-Case Subset Balancing Problems

Given a set of n input integers, the Equal Subset Sum problem asks us to find two distinct subsets with the same sum. In this paper we present an algorithm that runs in time O * (3 0.387n ) in the average case, significantly improving over the O * (3 0.488n ) running time of the best known worst-case algorithm [MNPW19] and the Meet-in-the-Middle benchmark of O * (3 0.5n ).

Our algorithm generalizes to a number of related problems, such as the "Generalized Equal Subset Sum" problem, which asks us to assign a coefficient c i from a set C to each input number x i such that i c i x i = 0. Our algorithm for the average-case version of this problem runs in time |C| (0.5-c0/|C|)n for some positive constant c 0 , whenever C = 0, ±1, . . . , ±d or ±1, . . . , ±d for some positive integer d (with runtime O * (|C| 0.45n ) when |C| < 10). Our results extend to the problem of finding "nearly balanced" solutions in which the target is a not-too-large nonzero offset τ .

Our approach relies on new structural results that characterize the probability that i c i x i = τ has a solution c ∈ C n when x i 's are chosen randomly; these results may be of independent interest. Our algorithm is inspired by the "representation technique" introduced by . This requires several new ideas to overcome preprocessing hurdles that arise in the representation framework, as well as a novel application of dynamic programming in the solution recovery phase of the algorithm.