%AChen, Xi%AJin, Yaonan%ARandolph, Tim%AServedio, Rocco%AMegow, Nicole Ed.%ASmith, Adam Ed.%D2023%IApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)
%KExact algorithms; subset sum; log shaving; Theory of computation → Design and analysis of algorithms
%MOSTI ID: 10501384
%PMedium: X
%TSubset Sum in Time 2^{n/2}/poly(n)
%XA major goal in the area of exact exponential algorithms is to give an algorithm for the (worst-case) n-input Subset Sum problem that runs in time 2^{(1/2 - c)n} for some constant c > 0. In this paper we give a Subset Sum algorithm with worst-case running time O(2^{n/2} ⋅ n^{-γ}) for a constant γ > 0.5023 in standard word RAM or circuit RAM models. To the best of our knowledge, this is the first improvement on the classical "meet-in-the-middle" algorithm for worst-case Subset Sum, due to Horowitz and Sahni, which can be implemented in time O(2^{n/2}) in these memory models [Horowitz and Sahni, 1974].
Our algorithm combines a number of different techniques, including the "representation method" introduced by Howgrave-Graham and Joux [Howgrave-Graham and Joux, 2010] and subsequent adaptations of the method in Austrin, Kaski, Koivisto, and Nederlof [Austrin et al., 2016], and Nederlof and Węgrzycki [Jesper Nederlof and Karol Wegrzycki, 2021], and "bit-packing" techniques used in the work of Baran, Demaine, and Pǎtraşcu [Baran et al., 2005] on subquadratic algorithms for 3SUM.
Country unknown/Code not availablehttps://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2023.39OSTI-MSA