8
$\begingroup$

Consider the following problems:

Orthogonal Vectors Problem

Input: A set $S$ of $n$ Boolean vectors each of length $d$.

Question: Do there exist distinct vectors $v_1$ and $v_2 \in S$ such that $v_1 \cdot v_2 = 0$?

Non-Orthogonal Vectors Problem

Input: A set $S$ of $n$ Boolean vectors each of length $d$ and a positive integer $k$.

Question: Do there exist distinct vectors $v_1$ and $v_2 \in S$ such that $v_1 \cdot v_2 \geq k$?

What is the relationship between these two problems?

In particular, here are a few more specific questions that I've been wondering about:

(1) Do either of these problems appear to be harder than the other?

(2) I'm not sure what the current state of the art algorithm is for OVP, but for either of these problems, can you get an upper bound better than $O(n^2 \cdot d)$ time?

(3) Does fixing $k$ make any difference for the second problem's complexity?

By $v_1 \cdot v_2$, I mean the inner product of $v_1$ and $v_2$ over $\mathbb{R^d}$.

Edit: Most of the responses offer really great insights when $d$ is small.

What can be said when $d$ is larger? Say $d = n$ or $d = \sqrt{n}$ or at least $d = n^\alpha$ for some $\alpha > 0$.

$\endgroup$
  • 4
    $\begingroup$ Regarding (2): as far as I know, the best known algorithm for solving OVP was established in this paper. It has complexity $$O\left(n^{2-\frac{1}{O\left(\log \left(\frac{d}{\log n}\right)\right)}}\right).$$ Improving this result to $O(n^{2-\varepsilon})$ for some constant $\varepsilon$ is a famous open problem, and believed to be unlikely, since it would falsify the strong exponential time hypothesis conjecture. $\endgroup$ – Geoffroy Couteau Sep 17 '18 at 10:20
  • $\begingroup$ The second problem is also solvable in $O(n * k * {d \choose k})$ time. Just choose $k$ positions, then check if two vectors have all 1's in those positions. $\endgroup$ – Michael Wehar Sep 18 '18 at 11:38
  • 1
    $\begingroup$ A note about the above time bound for OVP: the time bound also requires that d <= 2^(sqrt(log n)), otherwise the intermediate construction of a probabilistic polynomial takes too long. $\endgroup$ – Ryan Williams Sep 18 '18 at 16:59
  • 2
    $\begingroup$ About large d: Algorithms for rectangular matrix multiplication beat n^2 d in computing all dot products. When d<n^0.3 the time bound becomes n^(2+o(1)). $\endgroup$ – Rasmus Pagh Sep 19 '18 at 16:09
  • 1
    $\begingroup$ @MichaelWehar: Exactly. I think the best result is due to François Le Gall, arxiv.org/abs/1204.1111 $\endgroup$ – Rasmus Pagh Sep 20 '18 at 15:50
8
$\begingroup$

When $k$ is given as part of the input, the second problem is equivalent to the monochromatic Max-IP problem (given $S \subseteq \{0,1\}^d$, find $\max_{(a,b) \in S, a\ne b} a \cdot b$).

Recently I and Ryan Williams have an (unpublic yet) work showing that when $d = O(\log n)$, OVP and a bichromatic version of Max-IP (given $A,B$, find $\max_{(a,b) \in A \times B} a \cdot b$), is actually equivalent: that is, if one of them has $n^{2-\varepsilon}$ time algorithm, so does the other one. (The reduction from OVP to Max-IP is well-known, the new reduction here is that from Max-IP to OVP).

Since the monochromatic version of Max-IP can be reduced to the bichromatic version, the above result also implies that when $d = O(\log n)$, monochromatic Max-IP can be reduced to OVP.

I believe it is an open question that whether OVP can be reduced to monochromatic Max-IP. This is also closely related to establishing the OV-hardness for the closest pair problem (see e.g. On the Complexity of Closest Pair via Polar-Pair of Point-Sets)

For monochromatic Max-IP, there is an algorithm with running time $n^{2 - 1/\widetilde{O}((d/\log n)^{1/3})}$ time algorithm by Alman, Chan and Williams (also pointed out by Rasmus), for which I believe is the state of the art. While the best algorithm for OVP runs in $n^{2 - 1/O(\log c)}$ time when $d = c \log n$, which is significantly faster.

Also, the approximate version of Max-IP is also studied by this paper On The Hardness of Approximate and Exact (Bichromatic) Maximum Inner Product, which gives a characterization for the bichromatic case (that is, for which dimensions $d$ and approximate ratio $t$, the problem can be solved in $n^{2-\varepsilon}$ time?). The algorithm in that paper also works for the monochromatic case.

$\endgroup$
  • $\begingroup$ Does the $n^{2 - 1/\widetilde{O}((d/\log n)^{1/3})}$ time algorithm require some bounds on $d$? $\endgroup$ – Michael Wehar Jun 30 at 5:29
6
$\begingroup$

If $k=O(\log n)$ I believe the techniques of Alman, Chan, and Williams give the best known solution to the Non-Orthogonal Vectors Problem. (They phrase it differently, as a Hamming closest pair problem, but this is equivalent up to poly($d$) factors.)

With no bound on $k$, a bichromatic version of the Non-Orthogonal Vectors Problem is at least as hard as the Orthogonal Vectors Problem (OVP) up to a factor $d \log n$. First, note that with a factor $\log n$ overhead we can reduce to the bichromatic version of OVP where $S = S_1 \cup S_2$ (disjoint union into sets of different "color") and we are only interested in bichromatic orthogonal pairs $(v_1,v_2)\in S_1\times S_2$. Second, with a factor $d$ overhead we may reduce to the special case of bichromatic OVP where all vectors in $S_1$ have the same Hamming weight $w$. Finally, by inverting all vectors in $S_2$ to get $S'_2$ we see that $S_1$ and $S_2$ have an orthogonal pair if and only if $S_1$ and $S'_2$ have a pair of vectors with dot product at least $w$. I am not sure if there is an efficient reduction from the bichromatic Non-Orthogonal Vectors Problem to the monochromatic version you describe, though.

If you allow approximation there are a number of recent results for the bichromatic Non-Orthogonal Vectors Problem (often called the Maximum Inner Product Search problem). See e.g. this paper and its references.

$\endgroup$
0
$\begingroup$

Equivalences:

The non-orthogonal vectors problem (as defined above) for a set $S$ of $n$ Boolean vectors each of length $d$ and a positive integer $k$ is equivalent the following:

  • Finding a $2$ by $k$ submatrix of 1's in a given $n$ by $d$ Boolean matrix.

  • Finding a $\mathrm{K}_{2,k}$ complete subgraph in a given bipartite graph where the first vertex set has size $n$ and the second vertex set has size $d$.

Naive Algorithm:

The naive approach for the non-orthogonal vectors problem runs in $O(d \cdot n^2)$ time because it takes $O(d \cdot n^2)$ time to naively compute the dot product of every pair of vectors.

Answer to questions (2) & (3):

Yes, there are several algorithms that are more efficient in different cases.

First approach:

We can solve the non-orthogonal vectors problem in $O(d \cdot n + k \cdot n^2)$ time.

Note: Since the dot product of two length $d$ Boolean vectors must be bounded by $d$, the problem only makes sense when $k \leq d$.

Proof. Let a set $S$ of $n$ Boolean vectors each of length $d$ and a positive integer $k$ be given. Consider an enumeration $\{s_i\}_{i\in[n]}$of the elements of $S$.

Create a hashmap $m$ from pairs $(a,b) \in [n] \times [n]$ to $\mathbb{N}$. Initially, $m$ maps each input to the value 0.

For each $i \in [d]$, we do the following. Enumerate through pairs of vectors $s_a$, $s_b$ such that $a < b$, the $i$th bit of $s_a$ is 1, and the $i$th bit of $s_b$ is 1. For each such $s_a$ and $s_b$ if $m(a,b) = k - 1$, then $s_a$ and $s_b$ are non-orthogonal i.e. $s_a \cdot s_b \geq k$. Otherwise, increment $m(a,b)$ and continue.

If we finish the enumeration, then no pair of vectors are non-orthogonal.

It takes $O(n \cdot d)$ time to scan through every bit of every vector. Then, it takes additional time for enumerating pairs of vectors. Because there are at most ${n \choose 2}$ pairs of vectors and each pair can show up at most $k-1$ times before they've been shown to be non-orthogonal, enumerating pairs takes at most $O(k \cdot n^2)$ time. Therefore, the total runtime is $O(d \cdot n + k \cdot n^2)$.

Note: When $k = 2$, we can improve this approach to $O(n \cdot d)$ time. This is because when $k = 2$, we can reduce finding a pair of non-orthogonal vectors among $n$ Boolean vectors of length $d$ to finding a pair of non-orthogonal vectors among $d$ Boolean vectors of length $n$.

Second approach:

We can solve the non-orthogonal vectors problem in $O(k \cdot {d \choose k} \cdot n)$ time.

Proof. Let a set $S$ of $n$ Boolean vectors each of length $d$ and a positive integer $k$ be given.

Enumerate through sets $P \subseteq [d]$ such that $P$ has size $k$. For every vector $v \in S$, check if $v$ has all 1's at the positions in $P$. It there are two vectors that have all 1's at the positions in $P$, then we've found two non-orthogonal vectors.

In total, there are ${d \choose k}$ possible choices for $P$. And, for each choice, we scan through $k \cdot n$ bits from the vectors. Therefore, in total, the runtime is $O(k \cdot {d \choose k} \cdot n)$.

Third approach:

When $d \leq n$, we can solve the non-orthongal vectors problem in $O(d^{\omega - 2} \cdot n^2)$ time where $\omega$ is the exponent for integer matrix multiplication. When $d > n$, we can solve the non-orthongal vectors problem in $O(d \cdot n^{\omega - 1})$ time.

Note: As pointed out by @Rasmus Pagh, we can improve this algorithm to $O(n^{2 + o(1)})$ time when $d \leq n^{0.3}$. See here for more info: https://arxiv.org/abs/1204.1111

Proof. Let a set $S$ of $n$ Boolean vectors each of length $d$ and a positive integer $k$ be given.

Consider matrices $A$ and $B$. The first matrix $A$ has dimensions $n$ by $d$ where each row of $A$ is a vector from $S$. The second matrix $B$ has dimensions $d$ by $n$ where each column of $B$ is a vector from $S$.

We can compute the dot product of every pair of vectors in $S$ by computing $A \cdot B$ using algorithms for fast integer matrix multiplication.

When $d \leq n$, one approach is to convert the rectangular matrix multiplication into $(\frac{n}{d})^2$ multiplications of square $d$ by $d$ matrices. By using fast square matrix multiplication, we can compute all of the multiplications in $O((\frac{n}{d})^2 \cdot d^{\omega}) = O(d^{\omega - 2} \cdot n^2)$ time.

When $d > n$, one approach is to convert the rectangular matrix multiplication into $\frac{d}{n}$ multiplications of square $n$ by $n$ matrices. By using fast square matrix multiplication, we can compute all of the multiplications in $O((\frac{d}{n}) \cdot n^{\omega}) = O(d \cdot n^{\omega - 1})$ time.

$\endgroup$
  • $\begingroup$ Let's compare these three approaches in several different cases. Case 1: When $k$ is fixed and $d = O(\log^2(n))$, the second approach is most efficient. $\endgroup$ – Michael Wehar Jun 30 at 4:38
  • $\begingroup$ Case 2: When $k = O(\log^2(n))$ and $d=O(n^{\alpha})$ for any $\alpha \in (0.3,1)$, the first approach is sometimes most efficient. $\endgroup$ – Michael Wehar Jun 30 at 4:59
  • $\begingroup$ Case 3: When $d \leq n^{0.3}$, the third case is sometimes most efficient. $\endgroup$ – Michael Wehar Jun 30 at 5:00
  • $\begingroup$ Case 4: When $d$ and $k$ are larger than $n$, the third approach is sometimes most efficient. $\endgroup$ – Michael Wehar Jun 30 at 5:02
  • $\begingroup$ Note: The first approach is quite similar to the algorithm for finding a four cycle in a graph in quadratic time. See here: sciencedirect.com/science/article/pii/S0304020808730196 $\endgroup$ – Michael Wehar Jun 30 at 5:03

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.