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$
  • 3
    $\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$
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$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.