Pairwise comparison of bit vectors 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\}$.
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".) 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). 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) can be used to solve the average case in subquadratic time.