Faster space-efficient algorithms for subset sum and k-sum

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 Linear 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.5polylog(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.