  We present space efficient Monte Carlo algorithms that solve Subset Sum and
Knapsack instances with $n$ items using $O^*(2^{0.86n})$ time and polynomial
space, where the $O^*(\cdot)$ notation suppresses factors polynomial in the
input size. Both algorithms assume random read-only access to random bits.
Modulo this mild assumption, this resolves a long-standing open problem in
exact algorithms for NP-hard problems. 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\geq 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^2)$ time algorithm if no value occurs too often in the same list.
