<p>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.</p>

<p>Consequently, no such data structure exists.</p>

<hr>

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

<p>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.</p>

<p>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.</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 4.0
2018-08-16T05:55:07.157Z
For the uninitiated, can you summarize or provide reference to the precise form of the communication complexity statement you are using?
pre-kidney
CC BY-SA 4.0
2018-08-16T06:44:01.877Z
@pre-kidney, the result I refer to is a standard result.  You can read about communication complexity in a variety of places, and Google will turn up papers that refer to the result on the communication complexity of set disjointness.
D.W.
CC BY-SA 4.0
2018-08-16T07:14:08.793Z
Surely since it is such a standard result, it is not too much of a burden to ask you to point out a reference that states the specific version of the result you are using?
pre-kidney
CC BY-SA 4.0
2018-08-16T08:35:49.547Z
Just type "set disjointness communication complexity" into google.
Gamow
CC BY-SA 4.0
2018-08-16T13:21:00.513Z
According to [this survey](https://www.cs.toronto.edu/~toni/Papers/set-disjointness.pdf), linear lower bounds hold even for randomized communication complexity of set disjointness for subsets of $[n]$.  I'll add the caveat that the paper discusses at least two models for randomized communication complexity -- shared vs. private random bits -- but I'm not sure from a quick scan of the paper whether linear lower bounds apply to the shared-random-bits model.
Neal Young
CC BY-SA 4.0
2018-08-16T19:21:25.513Z
@pre-kidney, I've edited my answer to provide further explanation of the reduction I propose.  Others have explained how to find more about communication complexity and standard results on set disjointness.  Hopefully that will give you enough to work with that if you have concerns, you will be able to identify more specifically what the nature of your concern is.
D.W.
CC BY-SA 4.0
2018-08-17T08:43:45.423Z
@NealYoung It turns out that it doesn't matter because any public randomness protocol can be turned into a private randomness one at the cost of communicating $O(\log n)$ more bits. See for example these notes https://ocw.mit.edu/courses/mathematics/18-405j-advanced-complexity-theory-spring-2016/lecture-notes/MIT18_405JS16_Random.pdf
Sasho Nikolov
CC BY-SA 4.0
2018-08-16T05:39:21.910Z
2018-08-16T19:19:10.843Z
2018-08-16T19:19:10.843Z
D.W.
<p>This is not an answer to the exact question you pose, because the $n$ is different and the set instances are not separate. But there's a data structure for representing subsets of an $n$-element universe that allows addition of another subset $S$ in time $\tilde O(|S|)$ time and finding the smallest element at which two sets differ in time $O(\log n)$, in my paper "Rooted Cycle Bases" (JGAA 2017, <a href="http://jgaa.info/getPaper?id=434" rel="nofollow noreferrer">http://jgaa.info/getPaper?id=434</a>, section 5.2).</p>

CC BY-SA 4.0
2018-08-16T20:33:46.530Z
2018-08-17T00:34:39.343Z
2018-08-17T00:34:39.343Z
David Eppstein
<p>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.</p>

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

<ol>
<li><p>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.</p></li>
<li><p>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.</p></li>
</ol>

<p>Note: this is inspired by a comment on this unsolved question <a href="https://cs.stackexchange.com/questions/96222/find-common-min-in-logarithmic-time">https://cs.stackexchange.com/questions/96222/find-common-min-in-logarithmic-time</a></p>

CC BY-SA 4.0
2018-08-16T05:48:44.220Z
It is possible to solve your example problem in the other question in $O(n^2\log n)$. However your current question is completely different. E.g. for me it is not clear if the elements of the sets are comparable (hence it might lead to $\Omega(n^2)$ lowerbound), On the other hand even if they are integers, non-existence of an algorithm with o(n) running time doesn't mean there is no algorithm for n sets in $o(n^3)$.
Saeed
CC BY-SA 4.0
2018-08-16T05:51:58.903Z
@Saeed yes I agree this is a completely different question than the example problem in other question - that is why I separated it out and asked it separately. By the way, if you see a way to solve the example problem in the other question in O(n^2 log n), that would be very interesting and I would encourage you to post it as an answer over there (even if it does not necessarily lead to a data structure with the desired properties).
pre-kidney
CC BY-SA 4.0
2018-08-16T07:41:22.097Z
I'm not a member of that website so I cannot amswer there, if you ask it here me or someone else might answer your question. Anyways  I think your current question is neither well formalized nor is a research level question.
Saeed
CC BY-SA 4.0
2018-08-16T12:49:07.853Z
What is the universe of elements?  What operations can be done on those elements?  Do you require a deterministic data structure, or would it be enough to have a randomized one that works with high probability?
Neal Young
CC BY-SA 4.0
2018-08-16T13:03:19.787Z
E.g., if, say, your universe is $[1,c n]$ for some constant $c$, and your machine model allows constant-time bitwise operations on $(\log n)$-bit words, then surely (with $O(n)$-time initialization) you can check disjointness in $O(n/\log n)$ time.
Neal Young
CC BY-SA 4.0
2018-08-17T03:27:35.727Z
@NealYoung please see my more precise reformulation of the initial question.
pre-kidney
CC BY-SA 4.0
2018-08-17T03:34:25.110Z
Thanks.  FWIW, w.r.t. to your new formulation, I personally don't know what it means for one function to "factor as a composition of $f(n)$ elementary bitwise operations".  A-priori that condition sounds more like, say, the existence of a circuit of size $f(n)$ (which would not quite be equivalent to the existence of an $f(n)$-time algorithm, would it?)
Neal Young
<ds.data-structures><time-complexity><set-theory>
Data structure to determine if sets are disjoint in o(n) time
pre-kidney
# Data structure to determine if sets are disjoint in o(n) time

(Asked by: username_0 on 2018-08-16)

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?

1. 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.
2. 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>

**Tags:** ds.data-structures, time-complexity, set-theory

> **Comments:**
> **username_1**: It is possible to solve your example problem in the other question in $O(n^2\log n)$. However your current question is completely different. E.g. for me it is not clear if the elements of the sets are comparable (hence it might lead to $\Omega(n^2)$ lowerbound), On the other hand even if they are integers, non-existence of an algorithm with o(n) running time doesn't mean there is no algorithm for n sets in $o(n^3)$.  
> **username_0**: @username_1 yes I agree this is a completely different question than the example problem in other question - that is why I separated it out and asked it separately. By the way, if you see a way to solve the example problem in the other question in O(n^2 log n), that would be very interesting and I would encourage you to post it as an answer over there (even if it does not necessarily lead to a data structure with the desired properties).  
> **username_1**: I'm not a member of that website so I cannot amswer there, if you ask it here me or someone else might answer your question. Anyways  I think your current question is neither well formalized nor is a research level question.  
> **username_2**: What is the universe of elements?  What operations can be done on those elements?  Do you require a deterministic data structure, or would it be enough to have a randomized one that works with high probability?  
> **username_2**: E.g., if, say, your universe is $[1,c n]$ for some constant $c$, and your machine model allows constant-time bitwise operations on $(\log n)$-bit words, then surely (with $O(n)$-time initialization) you can check disjointness in $O(n/\log n)$ time.  
> **username_0**: @NealYoung please see my more precise reformulation of the initial question.  
> **username_2**: Thanks.  FWIW, w.r.t. to your new formulation, I personally don't know what it means for one function to "factor as a composition of $f(n)$ elementary bitwise operations".  A-priori that condition sounds more like, say, the existence of a circuit of size $f(n)$ (which would not quite be equivalent to the existence of an $f(n)$-time algorithm, would it?)  

---

## 2 answers

### Answer by username_3 on 2018-08-16. Score: 16

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.

> **Comments:**
> **username_0**: For the uninitiated, can you summarize or provide reference to the precise form of the communication complexity statement you are using?  
> **username_3**: @username_0, the result I refer to is a standard result.  You can read about communication complexity in a variety of places, and Google will turn up papers that refer to the result on the communication complexity of set disjointness.  
> **username_0**: Surely since it is such a standard result, it is not too much of a burden to ask you to point out a reference that states the specific version of the result you are using?  
> **username_4**: Just type "set disjointness communication complexity" into google.  
> **username_2**: According to [this survey](https://www.cs.toronto.edu/~toni/Papers/set-disjointness.pdf), linear lower bounds hold even for randomized communication complexity of set disjointness for subsets of $[n]$.  I'll add the caveat that the paper discusses at least two models for randomized communication complexity -- shared vs. private random bits -- but I'm not sure from a quick scan of the paper whether linear lower bounds apply to the shared-random-bits model.  
> **username_3**: @username_0, I've edited my answer to provide further explanation of the reduction I propose.  Others have explained how to find more about communication complexity and standard results on set disjointness.  Hopefully that will give you enough to work with that if you have concerns, you will be able to identify more specifically what the nature of your concern is.  
> **username_5**: @NealYoung It turns out that it doesn't matter because any public randomness protocol can be turned into a private randomness one at the cost of communicating $O(\log n)$ more bits. See for example these notes https://ocw.mit.edu/courses/mathematics/18-405j-advanced-complexity-theory-spring-2016/lecture-notes/MIT18_405JS16_Random.pdf  

---

### Answer by username_6 on 2018-08-16. Score: 6

This is not an answer to the exact question you pose, because the $n$ is different and the set instances are not separate. But there's a data structure for representing subsets of an $n$-element universe that allows addition of another subset $S$ in time $\tilde O(|S|)$ time and finding the smallest element at which two sets differ in time $O(\log n)$, in my paper "Rooted Cycle Bases" (JGAA 2017, <http://jgaa.info/getPaper?id=434>, section 5.2).


---

