Faster space-efficient algorithms for Subset Sum, k -Sum, and related problems

We present randomized algorithms that solve subset sum and knapsack instances with n items in O^∗ (2^0.86n) time, where the O^∗ (∙ ) notation suppresses factors polynomial in the input size, and polynomial space, assuming random read-only access to exponentially many random bits. These results can be extended to solve binary integer programming on n variables with few constraints in a similar running time. We also show that for any constant k ≥ 2, random instances of k-Sum can be solved using O(n^{k -0.5}polylog(n)) time and O(log n) space, without the assumption of random access to random bits.

Underlying these results is an algorithm that determines whether two given lists of length n with integers bounded by a polynomial in n share a common value. Assuming random read-only access to random bits, we show that this problem can be solved using O(log n) space significantly faster than the trivial O(n²) time algorithm if no value occurs too often in the same list.