<p>This problem is sometimes called <em>Subset Containment</em> and it is computationally equivalent to: <em>given $n$ sets $S_1,\ldots,S_n \subseteq [d]$, are there $i \neq j$ such that $S_i \cap S_j = \varnothing$?</em> (I believe the reduction is folklore and appears in several places, but one concrete reference is <a href="https://arxiv.org/abs/1407.4972">the arxiv paper "Into the Square"</a>.) In turn, this disjointness problem is identical to the (gradually becoming infamous) <em>Orthogonal Vectors</em> (OV) problem.</p>

<p>Therefore, algorithms for OV apply directly to this problem. Hence the problem can be solved in $O(2^d \cdot n)$ time, $O(n^{2-1/O(\log(d/\log n))})$ time, and so on (<a href="http://people.csail.mit.edu/rrw/faster-orthog-final.pdf">see for example, this SODA'15 paper</a>). Also, there is an $\tilde{O}(n + 2^d)$ time algorithm (I can give it, if you're interested). Furthermore, fine-grained hardness results for OV apply to the problem as well. For example, if it could be solved in $n^{1.999} 2^{o(d)}$ time in the worst case, then the Strong Exponential Time Hypothesis is false -- but don't let that stop you ;) </p>

<p>The "average case" (depending on how you define it) is generally easier and is (as far as we know) unrelated to Strong ETH; partial search data structures (such as <a href="https://people.csail.mit.edu/rivest/pubs/Riv76b.pdf">Rivest's work on partial search from the 1970s</a>) can be used to solve the average case in subquadratic time.</p>

CC BY-SA 3.0
2017-01-21T23:05:15.463Z
I am not the OP, but I am interested in your $\tilde{O}(n + 2^d)$ time algorithm.
jbapple
CC BY-SA 3.0
2017-01-21T23:47:35.140Z
It looks to me that Saeed's answer already suggests such an algorithm: build the "directed hypercube" DAG of $d2^d $ edges, mark the $n$ nodes which are in your input, and check if there's a path between two marked nodes. By dynamic programming ("propagating" the marks) this can be checked in one pass over the DAG by visiting nodes in increasing order of Hamming weight, spending $O(d) $ time at each node to check if a predecessor was marked.
Ryan Williams
CC BY-SA 3.0
2017-01-22T12:40:40.620Z
Maybe it is better to refer to my answer instead of writing "I can give it, if you're interested".
Saeed
CC BY-SA 3.0
2017-01-22T14:48:29.780Z
I had a different algorithm in mind, based on FFT. I admit I didn't look too closely at your original answer.
Ryan Williams
CC BY-SA 3.0
2017-01-22T15:53:07.050Z
I don't quite see how FFT can help at all. Before using FFT I guess one should define sort of good _hashing_ or structure to formulate it. I mean the point is not to use any special tool (like FFT, hashtable,  or any other possible magic). If you had really a different formulation then please provide it to make your answer richer and I also will understand my misunderstanding. Btw from the structure of the graph which is clear in first few lines of my answer the rest should be clear.
Saeed
CC BY-SA 3.0
2017-01-22T16:45:52.353Z
Think of the input as a mulitilinear polynomial in d variables (one variable in each dimension) and n monomials. To check for an orthogonal pair (equivalent to subset containment) you want to check if this polynomial squared has a monomial with no squares (multilinear monomial). You can do that in Otilde (2^d) time using a divide and conquer FFT like algorithm.
Ryan Williams
CC BY-SA 3.0
2017-01-23T09:00:07.250Z
I didn't get it exactly. I hope at least those people who upvote it understand it exactly and at least the whole conversation was useful for some (hopefully) wise people.
Saeed
CC BY-SA 3.0
2017-01-23T13:53:57.987Z
Saeed, feel free to email me for details, or if you're only confused about one part, ask about it. The full algorithm and proof would be a long answer. The idea is similar to arguments in http://dl.acm.org/citation.cfm?id=2885499 except you really don't need group algebra or randomization here, you just have to evaluate a d-variate polynomial on the "right" set of 2^d points. In general, FFTs let you do (even multivariate) polynomial multiplication more efficiently.
Ryan Williams
CC BY-SA 3.0
2017-01-23T15:55:09.440Z
Thanks Ryan, I actually didn't manage to figure out what was that set of points (I couldn't make a connection), it is maybe more than that and I may don't know what I don't understand, I'm not into that field e.g. I almost don't know anything about group algebra, but I know basics about similar usages of FFT. I may email you and ask for more information. Anyways thanks, I'll take a look at your linked paper.
Saeed
CC BY-SA 3.0
2017-01-21T17:04:09.230Z
2017-01-21T17:04:09.230Z
Ryan Williams
<p>Let suppose $d\le \log n$. We can define a DAG $D$ on $2^d$ vertices $v_1,\ldots,v_{2^d}$, we add edge from $v_i$ to $v_j$ in $D$ if the following conditions hold:</p>

<ol>
<li>bit representation of $i$ is smaller than bit representation of $j$ (w.r.t. the definition of $\le$ in the question), and </li>
<li>bit representation of $j$ has exactly one additional $1$ compare to $i$. </li>
</ol>

<p>For example we have an edge $1100\rightarrow 1101$ and an edge $1100\rightarrow 1110$ but there is no edge between $1100$ and $1111$ or there is no edge between $1101$ and $1110$.</p>

<p>Find corresponding vertices of $x_i$'s in this DAG ($x_i$ represents an integer $\ell$ and it corresponds to $v_\ell$) and colour those vertices. Call a coloured vertex $v$ a <em>coloured source</em> (or <em>source</em>), if there is no other coloured vertex which reaches $v$. With one BFS (from node 0), we can find all source vertices. Erase all colours (just a colour not vertices) except source colours. Find corresponding vertices of $y_i$'s and colour them with another colour. Start from one of the source vertices and run a BFS, once we find another coloured vertex we output that vertex together with the source, otherwise we mark the visited vertices of the graph and we continue BFS for other sources and over unvisited vertices. It is not hard to show that this algorithm finds a pair if it exists.</p>

<p>Time complexity: There are $2^d$ vertices in the graph,
every node has at most $d$ outgoing edges so total number of edges in the graph is at most $2^d d$. So the algorithm is $O(n\log n)$.</p>

<p>If $d$ is arbitrary, the above algorithm is $O (n+d 2^d)$, and per lowerbound in Ryan Williams answer, it is essentially tight.</p>

CC BY-SA 3.0
2017-01-21T01:51:46.270Z
Nice!  Can we use your algorithm as a building block to handle the case $d \gg \log n$, by restricting to a random subset of coordinates?  Suppose we define $d^* = (2/\lg(8/3)) \lg n \approx 1.4134 \lg n$, and assume $d^* < d$.  Randomly pick a subset of $d^*$ coordinates and restrict the $x_i$'s and $y_i'$ to those $d^*$ positions, obtaining $x_i^*,y_i^*$.  Now apply your algorithm to the $x_i^*,y_i^*$'s to find all pairs $i,j$ such that $x_i^* \le y_j^*$.  This takes $O(n^{1.4134} \log n)$ time.  (continued)
D.W.
CC BY-SA 3.0
2017-01-21T01:53:12.457Z
We expect to find $O(n^2 (3/4)^{d^*}) = O(n^2 \cdot n^{-0.5866}) = O(n^{1.41334})$ such pairs $i,j$ (since a fixed pair $x_i,y_j$ has a probability $3/4$ of meeting the condition in each selected coordinate), and for each such pair $i,j$ we can test whether $x_i \le y_j$.  It looks like the total running time is $O(n^{1.4134} \log n)$.  Does this sound right?
D.W.
CC BY-SA 3.0
2017-01-21T02:00:57.880Z
@D.W. It seems this is a precise randomised algorithm, and as you explained sounds the best possible when we want to find all pairs.
Saeed
CC BY-SA 3.0
2017-01-21T02:02:50.120Z
BTW I had something else in mind, I didn't think about randomised algorithm at all. It is very cool and nit though. I'm very sleepy right now, I'll be back tomorrow and will think once more about it and if I get something reasonable will update the answer and inform you.
Saeed
CC BY-SA 3.0
2017-01-21T05:47:27.977Z
I'll put here my ideas for $O(n d + d 2^d)$ solution. Maintain a hash set $M$. 
1. Iterate all sets $T_i$ (all the y's). For $T_i$ generate all of it's subsets and put each of them in $M$. This shall be done is top-down manner, i.e. generate the bigger subsets first. If we reach a subset $X$ that is already in $M$, we don't consider the subset of $X$ later. Thus for all iterations there'll be at most $2^d$ insertions in $M$, and exactly that much subsets will be generated. 
2. Iterate all sets $S_i$ (all the x's). For each $i$, check if $M$ contains $hash(S_i)$. If so we found a pair.
Marin Shalamanov
CC BY-SA 3.0
2017-01-21T05:49:04.443Z
Ok, I realized it's essentially the same as Saeed's solution.
Marin Shalamanov
CC BY-SA 3.0
2017-01-21T15:13:15.653Z
@D.W. Can you verify the update? If it is wrong or very purely written and not clear let me know.
Saeed
CC BY-SA 3.0
2017-01-21T15:14:35.057Z
@MarinShalamanov, I didn't completely get your idea, but I also thought about sort of hashing and that graph we make is kind of hash function which seems to be fit and useful for this problem.
Saeed
CC BY-SA 3.0
2017-01-21T16:18:38.317Z
Why is the number of sources at most $2^{d/2}$?  It seems to me it could be as large as, e.g., ${d \choose d/2} = \Theta(2^d/\sqrt{d})$ (if every bitvector containing $d/2$ bits set and $d/2$ bits clear is a source)... i.e., much bigger than $2^{d/2}$.  Can you justify that statement?
D.W.
CC BY-SA 3.0
2017-01-21T17:36:52.603Z
@D.W. that's true. I thought $d/2 \choose d $ is about $2^{d/2} \sqrt d$.
Saeed
CC BY-SA 3.0
2017-01-22T09:23:08.767Z
@D.W. Seems it is already best possible deterministic algorithm for small values of d. And if d is big then nothing is better than pairwise comparision. In fact with the generalized version the algorithm woks better than n^2 for d upto $d \in O (log^2 n)$
Saeed
CC BY-SA 3.0
2017-01-22T14:50:13.767Z
This algorithm is not close to "essentially tight". Consider the case of d >= 3 log n.
Ryan Williams
CC BY-SA 3.0
2017-01-22T16:23:00.173Z
For that range it is essentially tight. If you want to say it is bad for big d, doesn't need 3log n and just more than 2 log n suffices. I can generalize it to work better than trivial algorithm for bigger vaules of d. But it doesn't change essentially tightness of this one in the sense that I wrote.
Saeed
CC BY-SA 3.0
2017-01-21T01:01:29.580Z
2017-01-22T09:09:30.483Z
2017-01-22T09:09:30.483Z
Saeed
<p>Here is a divide-and-conquer algorithm with running time $O(n^{1.585})$, for arbitrary $d$, assuming the values are "random" and uniformly distributed.</p>

<p>Let $X^0$ denote the set of $x_i$'s that start with a 0 bit, and $X^1$ the set of $x_i$'s that start with a 1 bit.  Similarly define $Y^0$ and $Y^1$ to be the set of $y_i$'s that start with a 0 or 1 bit, respectively.  We expect that there will be about $n/2$ elements in each of these sets.</p>

<p>Now we'll recursively check whether there is an element of $X^0$ that is $\le$ an element of $Y^0$; an element of $X^0$ that is $\le$ an element of $Y^1$; or an element of $X^1$ that is $\le$ an element of $Y^1$.  The recursion bottom out when the set is of constant size.  The running time of this algorithm satisfies the recurrence</p>

<p>$$T(n) = 3 T(n/2) + O(1),$$</p>

<p>which has the solution $T(n) = O(n^{\lg 3}) = O(n^{1.585})$.</p>

CC BY-SA 3.0
2017-01-21T02:04:23.407Z
You may add your comments on my answer here. That looks actually promising.
Saeed
CC BY-SA 3.0
2017-01-21T01:47:02.483Z
2017-01-21T01:47:02.483Z
D.W.
<p>Define a partial order $\le$ on $\{0,1\}^d$ by pointwise comparison, i.e., we say $x \le y$ if $x_i \le y_i$ for all $i=1,2,\dots,d$.</p>

<p>I am interested in the following problem:</p>

<p>Given $x_1,\dots,x_n \in \{0,1\}^d$ and $y_1,\dots,y_n \in \{0,1\}^d$, I want to determine whether there exists $i,j$ such that $x_i \le y_j$.</p>

<p>How efficiently can this be solved?  Pairwise comparison requires $\Theta(n^2)$ comparisons.  Can we find a more efficient algorithm?</p>

<hr>

<p>I would be fine with assuming that the $x$'s and $y$'s come from some reasonable distribution and evaluating using the expected running time, if that helps.  We can assume $d$ is small compared to $n$.</p>

<p>Equivalent statement of the problem: Given sets $S_1,\dots,S_n$ and $T_1,\dots,T_n$, determine whether there exists $i,j$ such that $S_i \subseteq T_j$, where all sets are over the universe $\{1,2,\dots,d\}$.</p>

CC BY-SA 3.0
2017-01-20T23:45:38.587Z
Can we assume that $d = O(\log n)$ ?
Marin Shalamanov
CC BY-SA 3.0
2017-01-21T01:26:17.677Z
@MarinShalamanov, I would prefer an answer that doesn't restrict $d$ to be that small, if possible.
D.W.
CC BY-SA 3.0
2017-01-21T01:30:54.423Z
@D.W. It is a bit late to see your comment, I had another algorithm in mind but it was a bit complicated and I wasn't quite sure if it is correct, but I simplified it and provide something which works for small $d$. In fact vertices of the graph that I defined are some sort of representative for some sort of clusters (we can define artificial partial order on elements). We can make it a bit more clever to rely on $n$ not $d$ but needs some works and preciseness.
Saeed
CC BY-SA 3.0
2017-01-21T01:32:50.060Z
@Saeed, indeed -- I apologize!  Your algorithm is very clever and quite nice, and might be a good building block for handling larger $d$ as well.
D.W.
<ds.algorithms><co.combinatorics><ds.data-structures><partial-order>
Pairwise comparison of bit vectors
D.W.
# Pairwise comparison of bit vectors

(Asked by: username_0 on 2017-01-20)

Define a partial order $\le$ on $\{0,1\}^d$ by pointwise comparison, i.e., we say $x \le y$ if $x\_i \le y\_i$ for all $i=1,2,\dots,d$.

I am interested in the following problem:

Given $x\_1,\dots,x\_n \in \{0,1\}^d$ and $y\_1,\dots,y\_n \in \{0,1\}^d$, I want to determine whether there exists $i,j$ such that $x\_i \le y\_j$.

How efficiently can this be solved? Pairwise comparison requires $\Theta(n^2)$ comparisons. Can we find a more efficient algorithm?

---

I would be fine with assuming that the $x$'s and $y$'s come from some reasonable distribution and evaluating using the expected running time, if that helps. We can assume $d$ is small compared to $n$.

Equivalent statement of the problem: Given sets $S\_1,\dots,S\_n$ and $T\_1,\dots,T\_n$, determine whether there exists $i,j$ such that $S\_i \subseteq T\_j$, where all sets are over the universe $\{1,2,\dots,d\}$.

**Tags:** ds.algorithms, co.combinatorics, ds.data-structures, partial-order

> **Comments:**
> **username_1**: Can we assume that $d = O(\log n)$ ?  
> **username_0**: @MarinShalamanov, I would prefer an answer that doesn't restrict $d$ to be that small, if possible.  
> **username_2**: @username_0 It is a bit late to see your comment, I had another algorithm in mind but it was a bit complicated and I wasn't quite sure if it is correct, but I simplified it and provide something which works for small $d$. In fact vertices of the graph that I defined are some sort of representative for some sort of clusters (we can define artificial partial order on elements). We can make it a bit more clever to rely on $n$ not $d$ but needs some works and preciseness.  
> **username_0**: @username_2, indeed -- I apologize!  Your algorithm is very clever and quite nice, and might be a good building block for handling larger $d$ as well.  

---

## 3 answers

### Answer by username_3 on 2017-01-21. Score: 7

This problem is sometimes called *Subset Containment* and it is computationally equivalent to: *given $n$ sets $S\_1,\ldots,S\_n \subseteq [d]$, are there $i \neq j$ such that $S\_i \cap S\_j = \varnothing$?* (I believe the reduction is folklore and appears in several places, but one concrete reference is [the arxiv paper "Into the Square"](https://arxiv.org/abs/1407.4972).) In turn, this disjointness problem is identical to the (gradually becoming infamous) *Orthogonal Vectors* (OV) problem.

Therefore, algorithms for OV apply directly to this problem. Hence the problem can be solved in $O(2^d \cdot n)$ time, $O(n^{2-1/O(\log(d/\log n))})$ time, and so on ([see for example, this SODA'15 paper](http://people.csail.mit.edu/rrw/faster-orthog-final.pdf)). Also, there is an $\tilde{O}(n + 2^d)$ time algorithm (I can give it, if you're interested). Furthermore, fine-grained hardness results for OV apply to the problem as well. For example, if it could be solved in $n^{1.999} 2^{o(d)}$ time in the worst case, then the Strong Exponential Time Hypothesis is false -- but don't let that stop you ;)

The "average case" (depending on how you define it) is generally easier and is (as far as we know) unrelated to Strong ETH; partial search data structures (such as [Rivest's work on partial search from the 1970s](https://people.csail.mit.edu/rivest/pubs/Riv76b.pdf)) can be used to solve the average case in subquadratic time.

> **Comments:**
> **username_4**: I am not the OP, but I am interested in your $\tilde{O}(n + 2^d)$ time algorithm.  
> **username_3**: It looks to me that username_2's answer already suggests such an algorithm: build the "directed hypercube" DAG of $d2^d $ edges, mark the $n$ nodes which are in your input, and check if there's a path between two marked nodes. By dynamic programming ("propagating" the marks) this can be checked in one pass over the DAG by visiting nodes in increasing order of Hamming weight, spending $O(d) $ time at each node to check if a predecessor was marked.  
> **username_2**: Maybe it is better to refer to my answer instead of writing "I can give it, if you're interested".  
> **username_3**: I had a different algorithm in mind, based on FFT. I admit I didn't look too closely at your original answer.  
> **username_2**: I don't quite see how FFT can help at all. Before using FFT I guess one should define sort of good _hashing_ or structure to formulate it. I mean the point is not to use any special tool (like FFT, hashtable,  or any other possible magic). If you had really a different formulation then please provide it to make your answer richer and I also will understand my misunderstanding. Btw from the structure of the graph which is clear in first few lines of my answer the rest should be clear.  
> **username_3**: Think of the input as a mulitilinear polynomial in d variables (one variable in each dimension) and n monomials. To check for an orthogonal pair (equivalent to subset containment) you want to check if this polynomial squared has a monomial with no squares (multilinear monomial). You can do that in Otilde (2^d) time using a divide and conquer FFT like algorithm.  
> **username_2**: I didn't get it exactly. I hope at least those people who upvote it understand it exactly and at least the whole conversation was useful for some (hopefully) wise people.  
> **username_3**: username_2, feel free to email me for details, or if you're only confused about one part, ask about it. The full algorithm and proof would be a long answer. The idea is similar to arguments in http://dl.acm.org/citation.cfm?id=2885499 except you really don't need group algebra or randomization here, you just have to evaluate a d-variate polynomial on the "right" set of 2^d points. In general, FFTs let you do (even multivariate) polynomial multiplication more efficiently.  
> **username_2**: Thanks Ryan, I actually didn't manage to figure out what was that set of points (I couldn't make a connection), it is maybe more than that and I may don't know what I don't understand, I'm not into that field e.g. I almost don't know anything about group algebra, but I know basics about similar usages of FFT. I may email you and ask for more information. Anyways thanks, I'll take a look at your linked paper.  

---

### Answer by username_2 on 2017-01-21. Score: 3

Let suppose $d\le \log n$. We can define a DAG $D$ on $2^d$ vertices $v\_1,\ldots,v\_{2^d}$, we add edge from $v\_i$ to $v\_j$ in $D$ if the following conditions hold:

1. bit representation of $i$ is smaller than bit representation of $j$ (w.r.t. the definition of $\le$ in the question), and
2. bit representation of $j$ has exactly one additional $1$ compare to $i$.

For example we have an edge $1100\rightarrow 1101$ and an edge $1100\rightarrow 1110$ but there is no edge between $1100$ and $1111$ or there is no edge between $1101$ and $1110$.

Find corresponding vertices of $x\_i$'s in this DAG ($x\_i$ represents an integer $\ell$ and it corresponds to $v\_\ell$) and colour those vertices. Call a coloured vertex $v$ a *coloured source* (or *source*), if there is no other coloured vertex which reaches $v$. With one BFS (from node 0), we can find all source vertices. Erase all colours (just a colour not vertices) except source colours. Find corresponding vertices of $y\_i$'s and colour them with another colour. Start from one of the source vertices and run a BFS, once we find another coloured vertex we output that vertex together with the source, otherwise we mark the visited vertices of the graph and we continue BFS for other sources and over unvisited vertices. It is not hard to show that this algorithm finds a pair if it exists.

Time complexity: There are $2^d$ vertices in the graph,
every node has at most $d$ outgoing edges so total number of edges in the graph is at most $2^d d$. So the algorithm is $O(n\log n)$.

If $d$ is arbitrary, the above algorithm is $O (n+d 2^d)$, and per lowerbound in username_3 answer, it is essentially tight.

> **Comments:**
> **username_0**: Nice!  Can we use your algorithm as a building block to handle the case $d \gg \log n$, by restricting to a random subset of coordinates?  Suppose we define $d^* = (2/\lg(8/3)) \lg n \approx 1.4134 \lg n$, and assume $d^* < d$.  Randomly pick a subset of $d^*$ coordinates and restrict the $x_i$'s and $y_i'$ to those $d^*$ positions, obtaining $x_i^*,y_i^*$.  Now apply your algorithm to the $x_i^*,y_i^*$'s to find all pairs $i,j$ such that $x_i^* \le y_j^*$.  This takes $O(n^{1.4134} \log n)$ time.  (continued)  
> **username_0**: We expect to find $O(n^2 (3/4)^{d^*}) = O(n^2 \cdot n^{-0.5866}) = O(n^{1.41334})$ such pairs $i,j$ (since a fixed pair $x_i,y_j$ has a probability $3/4$ of meeting the condition in each selected coordinate), and for each such pair $i,j$ we can test whether $x_i \le y_j$.  It looks like the total running time is $O(n^{1.4134} \log n)$.  Does this sound right?  
> **username_2**: @username_0 It seems this is a precise randomised algorithm, and as you explained sounds the best possible when we want to find all pairs.  
> **username_2**: BTW I had something else in mind, I didn't think about randomised algorithm at all. It is very cool and nit though. I'm very sleepy right now, I'll be back tomorrow and will think once more about it and if I get something reasonable will update the answer and inform you.  
> **username_1**: I'll put here my ideas for $O(n d + d 2^d)$ solution. Maintain a hash set $M$.  1. Iterate all sets $T_i$ (all the y's). For $T_i$ generate all of it's subsets and put each of them in $M$. This shall be done is top-down manner, i.e. generate the bigger subsets first. If we reach a subset $X$ that is already in $M$, we don't consider the subset of $X$ later. Thus for all iterations there'll be at most $2^d$ insertions in $M$, and exactly that much subsets will be generated.  2. Iterate all sets $S_i$ (all the x's). For each $i$, check if $M$ contains $hash(S_i)$. If so we found a pair.  
> **username_1**: Ok, I realized it's essentially the same as username_2's solution.  
> **username_2**: @username_0 Can you verify the update? If it is wrong or very purely written and not clear let me know.  
> **username_2**: @MarinShalamanov, I didn't completely get your idea, but I also thought about sort of hashing and that graph we make is kind of hash function which seems to be fit and useful for this problem.  
> **username_0**: Why is the number of sources at most $2^{d/2}$?  It seems to me it could be as large as, e.g., ${d \choose d/2} = \Theta(2^d/\sqrt{d})$ (if every bitvector containing $d/2$ bits set and $d/2$ bits clear is a source)... i.e., much bigger than $2^{d/2}$.  Can you justify that statement?  
> **username_2**: @username_0 that's true. I thought $d/2 \choose d $ is about $2^{d/2} \sqrt d$.  
> **username_2**: @username_0 Seems it is already best possible deterministic algorithm for small values of d. And if d is big then nothing is better than pairwise comparision. In fact with the generalized version the algorithm woks better than n^2 for d upto $d \in O (log^2 n)$  
> **username_3**: This algorithm is not close to "essentially tight". Consider the case of d >= 3 log n.  
> **username_2**: For that range it is essentially tight. If you want to say it is bad for big d, doesn't need 3log n and just more than 2 log n suffices. I can generalize it to work better than trivial algorithm for bigger vaules of d. But it doesn't change essentially tightness of this one in the sense that I wrote.  

---

### Answer by username_0 on 2017-01-21. Score: 2

Here is a divide-and-conquer algorithm with running time $O(n^{1.585})$, for arbitrary $d$, assuming the values are "random" and uniformly distributed.

Let $X^0$ denote the set of $x\_i$'s that start with a 0 bit, and $X^1$ the set of $x\_i$'s that start with a 1 bit. Similarly define $Y^0$ and $Y^1$ to be the set of $y\_i$'s that start with a 0 or 1 bit, respectively. We expect that there will be about $n/2$ elements in each of these sets.

Now we'll recursively check whether there is an element of $X^0$ that is $\le$ an element of $Y^0$; an element of $X^0$ that is $\le$ an element of $Y^1$; or an element of $X^1$ that is $\le$ an element of $Y^1$. The recursion bottom out when the set is of constant size. The running time of this algorithm satisfies the recurrence

$$T(n) = 3 T(n/2) + O(1),$$

which has the solution $T(n) = O(n^{\lg 3}) = O(n^{1.585})$.

> **Comments:**
> **username_2**: You may add your comments on my answer here. That looks actually promising.  

---

