Finding a pair of non-overlapping bit vectors
Warmup: random bitvectors

As a warm-up, we can start with the case where each bitvector is chosen iid uniformly at random.  Then it turns out that the problem can be solved in $O(n^{1.6} \min(k, \lg n))$ time (more precisely, the $1.6$ can be replaced with $\lg 3$).

We'll consider the following two-set variant of the problem:

Given sets $S,T \subseteq \{0,1\}^k$ of bitvectors, determine where there exists a non-overlapping pair $s \in S, t \in T$.

The basic technique to solve this is divide-and-conquer.  Here is a $O(n^{1.6} k)$ time algorithm using divide-and-conquer:


Split $S$ and $T$ based upon the first bit position.  In other words, form $S_0 = \{s \in S : s_0=0\}$, $S_1 = \{s \in S : s_0 = 1\}$, $T_0 = \{t \in T : t_0 = 0\}$, $T_1 = \{t \in T : t_0 = 1\}$.
Now recursively look for a non-overlapping pair from $S_0,T_0$, from $S_0,T_1$, and from $T_1,S_0$.  If any recursive call finds a non-overlapping pair, output it, otherwise output "No overlapping pair exists".


Since all bitvectors are chosen at random, we can expect $|S_b| \approx |S|/2$ and $|T_b| \approx |T|/2$.  Thus, we have three recursive calls, and we've reduced the size of the problem by a factor of two (both sets are reduced in size by a factor of two).  After $\lg \min(|S|,|T|)$ splits, one of the two sets is down to size 1, and the problem can be solved in linear time.  We get a recurrence relation along the lines of $T(n) = 3T(n/2) + O(nk)$, whose solution is $T(n) = O(n^{1.6} k)$.  Accounting for running time more precisely in the two-set case, we see the running time is $O(\min(|S|,|T|)^{0.6} \max(|S|,|T|) k)$.

This can be further improved, by noting that if $k \ge 2.5\lg n+100$, then the probability that a non-overlapping pair exists is exponentially small.  In particular, if $x,y$ are two random vectors, the probability that they're non-overlapping is $(3/4)^k$.  If $|S|=|T|=n$, there are $n^2$ such pairs, so by a union bound, the probability a non-overlapping pair exists is at most $n^2 (3/4)^k$.  When $k \ge 2.5 \lg n+100$, this is $\le 1/2^{100}$.  So, as a pre-processing step, if $k \ge 2.5 \lg n + 100$, then we can immediately return "No non-overlapping pair exists" (the probability this is incorrect is negligibly small), otherwise we run the above algorithm.

Thus we achieve a running time of $O(n^{1.6} \min(k, \lg n))$ (or $O(\min(|S|,|T|)^{0.6} \max(|S|,|T|) \min(k, \lg n))$ for the two-set variant proposed above), for the special case where the bitvectors are chosen uniformly at random.

Of course, this is not a worst-case analysis.  Random bitvectors are considerably easier than the worst case -- but let's treat it as a warmup, to get some ideas that perhaps we can apply to the general case.

Lessons from the warmup

We can learn a few lessons from the warmup above.  First, divide-and-conquer (splitting on a bit position) seems helpful.  Second, you want to split on a bit position with as many $1$'s in that position as possible; the more $0$'s there are, the less reduction in subproblem size you get.

Third, this suggests that the problem gets harder as the density of $1$'s gets smaller -- if there are very few $1$'s among the bitvectors (they are mostly $0$'s), the problem looks quite hard, as each split reduces the size of the subproblems a little bit.  So, define the density $\Delta$ to be the fraction of bits that are $1$ (i.e., out of all $nk$ bits), and the density of bit position $i$ to be the fraction of bitvectors that are $1$ at position $i$.

Handling very low density

As a next step, we might wonder what happens if the density is extremely small.  It turns out that if the density in every bit position is smaller than $1/\sqrt{k}$, we're guaranteed that a non-overlapping pair exists: there is a (non-constructive) existence argument showing that some non-overlapping pair must exist.  This doesn't help us find it, but at least we know it exists.

Why is this the case?  Let's say that a pair of bitvectors $x,y$ is covered by bit position $i$ if $x_i=y_i=1$.  Note that every pair of overlapping bitvectors must be covered by some bit position.  Now, if we fix a particular bit position $i$, the number of pairs that can be covered by that bit position is at most $(n \Delta(i))^2 &lt; n^2/k$.  Summing across all $k$ of the bit positions, we find that the total number of pairs that are covered by some bit position is $&lt; n^2$.  This means there must exist some pair that's not covered by any bit position, which implies that this pair is non-overlapping.  So if the density is sufficiently low in every bit position, then a non-overlapping pair surely exists.

However, I'm at a loss to identify a fast algorithm to find such a non-overlapping pair, in these regime, even though one is guaranteed to exist.  I don't immediately see any techniques that would yield a running time that has a sub-quadratic dependence on $n$.  So, this is a nice special case to focus on, if you want to spend some time thinking about this problem.

Towards a general-case algorithm

In the general case, a natural heuristic seems to be: pick the bit position $i$ with the most number of $1$'s (i.e., with the highest density), and split on it.  In other words:


Find a bit position $i$ that maximizes $\Delta(i)$.
Split $S$ and $T$ based upon bit position $i$.  In other words, form $S_0 = \{s \in S : s_i=0\}$, $S_1 = \{s \in S : s_i = 1\}$, $T_0 = \{t \in T : t_i = 0\}$, $T_1 = \{t \in T : t_i = 1\}$.
Now recursively look for a non-overlapping pair from $S_0,T_0$, from $S_0,T_1$, and from $T_1,S_0$.  If any recursive call finds a non-overlapping pair, output it, otherwise output "No overlapping pair exists".


The challenge is to analyze its performance in the worst case.

Let's assume that as a pre-processing step we first compute the density of every bit position.  Also, if $\Delta(i) &lt; 1/\sqrt{k}$ for every $i$, assume that the pre-processing step outputs "An overlapping pair exists" (I realize that this doesn't exhibit an example of an overlapping pair, but let's set that aside as a separate challenge).  All this can be done in $O(nk)$ time.  The density information can be maintained efficiently as we do recursive calls; it won't be the dominant contributor to running time.

What will the running time of this procedure be?  I'm not sure, but here are a few observations that might help.  Each level of recursion reduces the problem size by about $n/\sqrt{k}$ bitvectors (e.g., from $n$ bitvectors to $n-n/\sqrt{k}$ bitvectors).  Therefore, the recursion can only go about $\sqrt{k}$ levels deep.  However, I'm not immediately sure how to count the number of leaves in the recursion tree (there are a lot less than $3^{\sqrt{k}}$ leaves), so I'm not sure what running time this should lead to.