Pairwise comparison of bit vectors

Question

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\}$.

Answer 1

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.

Answer 2

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 Ryan Williams answer, it is essentially tight.

Answer 3

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