Subset Sum in Time $2^{n\mathrm{/}2}\mathrm{/}poly(n)$

A 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\mathrm{/}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\mathrm{/}2}\cdot n^{-\gamma })$ for a constant $\gamma >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. Our algorithm combines a number of different techniques, including the representation method’’ introduced by Howgrave-Graham and Joux and subsequent adaptations of the method in Austrin, Kaski, Koivisto, and Nederlof, and Nederlof and Wegrzycki, and ``bit-packing’’ techniques used in the work of Baran, Demaine, and Patrascu on subquadratic algorithms for 3SUM.