5
$\begingroup$

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

Improve this question
$\endgroup$
7
  • $\begingroup$ 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)$. $\endgroup$ – Saeed Aug 16 '18 at 5:48
  • $\begingroup$ @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). $\endgroup$ – pre-kidney Aug 16 '18 at 5:51
  • $\begingroup$ 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. $\endgroup$ – Saeed Aug 16 '18 at 7:41
  • $\begingroup$ 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? $\endgroup$ – Neal Young Aug 16 '18 at 12:49
  • 1
    $\begingroup$ 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?) $\endgroup$ – Neal Young Aug 17 '18 at 3:34
16
$\begingroup$

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.

Improve this answer
$\endgroup$
7
  • $\begingroup$ For the uninitiated, can you summarize or provide reference to the precise form of the communication complexity statement you are using? $\endgroup$ – pre-kidney Aug 16 '18 at 5:55
  • 5
    $\begingroup$ Just type "set disjointness communication complexity" into google. $\endgroup$ – Gamow Aug 16 '18 at 8:35
  • 1
    $\begingroup$ According to this survey, 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. $\endgroup$ – Neal Young Aug 16 '18 at 13:21
  • 1
    $\begingroup$ @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. $\endgroup$ – D.W. Aug 16 '18 at 19:21
  • 1
    $\begingroup$ @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 ocw.mit.edu/courses/mathematics/… $\endgroup$ – Sasho Nikolov Aug 17 '18 at 8:43
6
$\begingroup$

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).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.