SODA Conference 2022 Conference Paper
Average-Case Subset Balancing Problems
- Xi Chen 0001
- Yaonan Jin
- Tim Randolph 0001
- Rocco A. Servedio
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. 387 n ) in the average case, significantly improving over the O ∗(3 0. 488 n ) running time of the best known worst-case algorithm [MNPW19] and the Meet-in-the-Middle benchmark of O ∗(3 0. 5 n ). 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 for some positive constant c 0, whenever C = {0, ± 1, …, ± d} or {±1, …, ± d } for some positive integer d (with runtime O ∗( |C| 0. 45 n ) 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 Howgrave-Graham and Joux [HGJ10]. 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.