How much better is this than prior art?
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.
The rules say
> Text surrounded by asterisks is italicized, if the character after the first asterisk isn't whitespace.
But apparently noen of the zero-width spaces are not counted as whitespace.