Space-Efficient Las Vegas Algorithms for K-SUM

Using hashing techniques, this paper develops a family of space-efficient Las Vegas randomized algorithms for $k$-SUM problems. This family includes an algorithm that can solve 3-SUM in $O(n^2)$ time and $O(\sqrt{n})$ space. It also establishes a new time-space upper bound for SUBSET-SUM, which can be solved by a Las Vegas algorithm in $O^{\ast }(2^{(1-\sqrt{\text{8}\mathrm{/}9\beta })n})$ time and $O^{\ast }(2^{\beta n})$ space, for any $\beta \in [0,\text{9}\mathrm{/}32]$.