Data structure to determine if sets are disjoint in o(n) time My initial question was exactly the title of this post, but after feedback from commenters I have formulated a more precise version of the question that attempts to capture its essence.

Does there exist an encoding of length-$n$ bit strings with the following properties?


The encoding can be computed in $o(n^2)$ time and space, i.e., the encoding $e\colon \{0,1\}^n\to \{0,1\}^{o(n^2)}$ factors as a composition of $o(n^2)$ elementary bitwise operations.
There exists an algorithm computing the disjoint set function with respect to this encoding in $o(n)$ time, i.e., the disjoint set function $e\bigl(\{0,1\}^n\bigr)^2\to \{0,1\}$ factors as a composition of $o(n)$ elementary bitwise operations.


Note: this is inspired by a comment on this unsolved question https://cs.stackexchange.com/questions/96222/find-common-min-in-logarithmic-time
The communication complexity of the set disjointness problem is $\Omega(n)$.  The communication complexity is a lower bound on the time complexity of testing whether the two instances are disjoint.  Imagine Alice stores the data structure for the first set, and Bob stores the data structure for the second set; since they'll have to communicate $\Omega(n)$ bits to determine whether their sets are disjoint, any algorithm that works on these two data structures will also necessarily involve doing at least that much computation.  It follows that testing disjointness of these two sets must take $\Omega(n)$ time, no matter what data structure you use, as long as each data structure is initialized separately.

Consequently, no such data structure exists.



Details: I'll elaborate on the proof more carefully, by sketching the reduction.

Suppose there was such a data structure, together with an algorithm $A$ that lets you test disjointness in $o(n)$ time.  Since it runs in $o(n)$ time, it must involve examining at most $o(n)$ bits of data, and in particular, at most $o(n)$ bits of the data structure for the first set and at most $o(n)$ bits of the data structure of the second set.

So, here is a communication protocol for set disjointness.  Initially, Alice initializes an instance of the data structure with her set, and Bob does the same with his set.  Start running algorithm $A$, with both of them executing the algorithm in lockstep.  Any time that algorithm $A$ examines a bit of the first data structure, Alice sends that bit to Bob.  Any time that the algorithm examines a bit of the second data structure sends that bit to Bob.  Now both Alice and Bob can execute the algorithm to completion.  At the end of the algorithm, both Alice and Bob know whether their sets are disjoint are not.  Also, the computation has taken $o(n)$ time, and they have sent only $o(n)$ bits of data (since it runs in $o(n)$ time, it can't send more than that), so we have a protocol for set disjointness with communication complexity $o(n)$.  This is impossible, so our original assumption that such an algorithm $A$ exists must also have been impossible as well.

If algorithm $A$ is randomized, then it's easy enough to send the random bits to both parties.  This doesn't affect the asymptotic complexity.

If the algorithm is in the RAM model, it can access $O(\log n)$ bits in a single operation, so we need to modify the above reduction slightly: if there is an algorithm $A$ for set disjointness that runs in $o(n/\log n)$ time, we obtain a communication protocol that sends $o(n)$ bits.  It follows that any algorithm $A$ for set disjointness must take at least $\Omega(n/\log n)$ time in the RAM model.  Since the RAM model is a standard assumption, perhaps it would be more reasonable to summarize this result as implying that disjointness queries must take at least $\Omega(n / \log n)$ time, in the worst case, no matter what data structure you use, as long as each instance of the data structure is initialized separately.