In pure time terms it is worse, as the best prior was O$(2^.5n). However, that algorithm took O$(2^.25n) space. This algorithm uses only polynomial space but ru

In pure time terms it is worse, as the best prior was O$(2^.5n). However, that algorithm took O$(2^.25n) space. This algorithm uses only polynomial space but runs in O$(2^.86n) time. The naive solution runs in O$(2^n) and polynomial space. I believe this top line result will mostly be of interest to Computer Scientists, as a practical matter these problems are rarely solved exactly because even the fast algorithms are far too slow for non-trivial problem sizes. However, this part regarding the "list disjointment problem" may be of wider interest: "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." N.B. The HN parser won't let me use stars, so read star for each of the dollar signs in the first paragraph.