<p><strong>Equivalences:</strong></p>

<blockquote>
  <p>The non-orthogonal vectors problem (as defined above) for a set <span class="math-container">$S$</span> of <span class="math-container">$n$</span> Boolean
  vectors each of length <span class="math-container">$d$</span> and a positive integer <span class="math-container">$k$</span> is equivalent
  the following:</p>
  
  <ul>
  <li><p>Finding a <span class="math-container">$2$</span> by <span class="math-container">$k$</span> submatrix of 1's in a given <span class="math-container">$n$</span> by <span class="math-container">$d$</span> Boolean matrix.</p></li>
  <li><p>Finding a <span class="math-container">$\mathrm{K}_{2,k}$</span> complete subgraph in a given bipartite graph where the first vertex set has size <span class="math-container">$n$</span> and the second vertex
  set has size <span class="math-container">$d$</span>.</p></li>
  </ul>
</blockquote>

<p><strong>Naive Algorithm:</strong></p>

<blockquote>
  <p>The naive approach for the non-orthogonal vectors problem runs in <span class="math-container">$O(d \cdot n^2)$</span> time because it takes <span class="math-container">$O(d \cdot n^2)$</span> time to naively compute the dot product of every pair of vectors.</p>
</blockquote>

<p><strong>Answer to questions (2) &amp; (3):</strong></p>

<blockquote>
  <p>Yes, there are several algorithms that are more efficient in different
  cases.</p>
</blockquote>

<p><strong>First approach:</strong></p>

<blockquote>
  <p>We can solve the non-orthogonal vectors problem in <span class="math-container">$O(d \cdot n + k \cdot n^2)$</span> time.</p>
  
  <p><em>Note:</em> Since the dot product of two length <span class="math-container">$d$</span> Boolean vectors must be bounded by <span class="math-container">$d$</span>, the problem only makes sense when <span class="math-container">$k \leq d$</span>.</p>
  
  <p><strong>Proof.</strong>  Let a set <span class="math-container">$S$</span> of <span class="math-container">$n$</span> Boolean vectors each of length <span class="math-container">$d$</span> and a positive integer <span class="math-container">$k$</span> be given.  Consider an enumeration <span class="math-container">$\{s_i\}_{i\in[n]}$</span>of the elements of <span class="math-container">$S$</span>.</p>
  
  <p>Create a hashmap <span class="math-container">$m$</span> from pairs <span class="math-container">$(a,b) \in [n] \times [n]$</span> to <span class="math-container">$\mathbb{N}$</span>.  Initially, <span class="math-container">$m$</span> maps each input to the value 0.</p>
  
  <p>For each <span class="math-container">$i \in [d]$</span>, we do the following.  Enumerate through pairs of vectors <span class="math-container">$s_a$</span>, <span class="math-container">$s_b$</span> such that <span class="math-container">$a &lt; b$</span>, the <span class="math-container">$i$</span>th bit of <span class="math-container">$s_a$</span> is 1, and the <span class="math-container">$i$</span>th bit of <span class="math-container">$s_b$</span> is 1.  For each such <span class="math-container">$s_a$</span> and <span class="math-container">$s_b$</span> if <span class="math-container">$m(a,b) = k - 1$</span>, then <span class="math-container">$s_a$</span> and <span class="math-container">$s_b$</span> are non-orthogonal i.e. <span class="math-container">$s_a \cdot s_b \geq k$</span>.  Otherwise, increment <span class="math-container">$m(a,b)$</span> and continue.</p>
  
  <p>If we finish the enumeration, then no pair of vectors are non-orthogonal. </p>
  
  <p>It takes <span class="math-container">$O(n \cdot d)$</span> time to scan through every bit of every vector.  Then, it takes additional time for enumerating pairs of vectors.  Because there are at most <span class="math-container">${n \choose 2}$</span> pairs of vectors and each pair can show up at most <span class="math-container">$k-1$</span> times before they've been shown to be non-orthogonal, enumerating pairs takes at most <span class="math-container">$O(k \cdot n^2)$</span> time.  Therefore, the total runtime is <span class="math-container">$O(d \cdot n + k \cdot n^2)$</span>.</p>
  
  <p><em>Note:</em> When <span class="math-container">$k = 2$</span>, we can improve this approach to <span class="math-container">$O(n \cdot d)$</span> time. 
   This is because when <span class="math-container">$k = 2$</span>, we can reduce finding a pair of non-orthogonal vectors among <span class="math-container">$n$</span> Boolean vectors of length <span class="math-container">$d$</span> to finding a pair of non-orthogonal vectors among <span class="math-container">$d$</span> Boolean vectors of length <span class="math-container">$n$</span>.</p>
</blockquote>

<p><strong>Second approach:</strong></p>

<blockquote>
  <p>We can solve the non-orthogonal vectors problem in <span class="math-container">$O(k \cdot {d \choose k} \cdot n)$</span> time.</p>
  
  <p><strong>Proof.</strong> Let a set <span class="math-container">$S$</span> of <span class="math-container">$n$</span> Boolean vectors each of length <span class="math-container">$d$</span> and a positive integer <span class="math-container">$k$</span> be given.</p>
  
  <p>Enumerate through sets <span class="math-container">$P \subseteq [d]$</span> such that <span class="math-container">$P$</span> has size <span class="math-container">$k$</span>.  For every vector <span class="math-container">$v \in S$</span>, check if <span class="math-container">$v$</span> has all 1's at the positions in <span class="math-container">$P$</span>.  It there are two vectors that have all 1's at the positions in <span class="math-container">$P$</span>, then we've found two non-orthogonal vectors.</p>
  
  <p>In total, there are <span class="math-container">${d \choose k}$</span> possible choices for <span class="math-container">$P$</span>.  And, for each choice, we scan through <span class="math-container">$k \cdot n$</span> bits from the vectors.  Therefore, in total, the runtime is <span class="math-container">$O(k \cdot {d \choose k} \cdot n)$</span>.</p>
</blockquote>

<p><strong>Third approach:</strong></p>

<blockquote>
  <p>When <span class="math-container">$d \leq n$</span>, we can solve the non-orthongal vectors problem in <span class="math-container">$O(d^{\omega - 2} \cdot n^2)$</span> time where <span class="math-container">$\omega$</span> is the exponent for integer matrix multiplication.  When <span class="math-container">$d &gt; n$</span>, we can solve the non-orthongal vectors problem in <span class="math-container">$O(d \cdot n^{\omega - 1})$</span> time.</p>
  
  <p><em>Note:</em> As pointed out by @Rasmus Pagh, we can improve this algorithm to <span class="math-container">$O(n^{2 + o(1)})$</span> time when <span class="math-container">$d \leq n^{0.3}$</span>.  See here for more info: <a href="https://arxiv.org/abs/1204.1111" rel="nofollow noreferrer">https://arxiv.org/abs/1204.1111</a></p>
  
  <p><strong>Proof.</strong> Let a set <span class="math-container">$S$</span> of <span class="math-container">$n$</span> Boolean vectors each of length <span class="math-container">$d$</span> and a positive integer <span class="math-container">$k$</span> be given.</p>
  
  <p>Consider matrices <span class="math-container">$A$</span> and <span class="math-container">$B$</span>.  The first matrix <span class="math-container">$A$</span> has dimensions <span class="math-container">$n$</span> by <span class="math-container">$d$</span> where each row of <span class="math-container">$A$</span> is a vector from <span class="math-container">$S$</span>.  The second matrix <span class="math-container">$B$</span> has dimensions <span class="math-container">$d$</span> by <span class="math-container">$n$</span> where each column of <span class="math-container">$B$</span> is a vector from <span class="math-container">$S$</span>.</p>
  
  <p>We can compute the dot product of every pair of vectors in <span class="math-container">$S$</span> by computing <span class="math-container">$A \cdot B$</span> using algorithms for fast integer matrix multiplication.</p>
  
  <p>When <span class="math-container">$d \leq n$</span>, one approach is to convert the rectangular matrix multiplication into <span class="math-container">$(\frac{n}{d})^2$</span> multiplications of square <span class="math-container">$d$</span> by <span class="math-container">$d$</span> matrices.  By using fast square matrix multiplication, we can compute all of the multiplications in <span class="math-container">$O((\frac{n}{d})^2 \cdot d^{\omega}) = O(d^{\omega - 2} \cdot n^2)$</span> time.</p>
  
  <p>When <span class="math-container">$d &gt; n$</span>, one approach is to convert the rectangular matrix multiplication into <span class="math-container">$\frac{d}{n}$</span> multiplications of square <span class="math-container">$n$</span> by <span class="math-container">$n$</span> matrices.  By using fast square matrix multiplication, we can compute all of the multiplications in <span class="math-container">$O((\frac{d}{n}) \cdot n^{\omega}) = O(d \cdot n^{\omega - 1})$</span> time.</p>
</blockquote>

CC BY-SA 4.0
2019-06-30T04:38:25.580Z
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.
Michael Wehar
CC BY-SA 4.0
2019-06-30T04:59:20.587Z
**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.
Michael Wehar
CC BY-SA 4.0
2019-06-30T05:00:23.007Z
**Case 3:** When $d \leq n^{0.3}$, the third case is sometimes most efficient.
Michael Wehar
CC BY-SA 4.0
2019-06-30T05:02:03.787Z
**Case 4:** When $d$ and $k$ are larger than $n$, the third approach is sometimes most efficient.
Michael Wehar
CC BY-SA 4.0
2019-06-30T05:03:10.797Z
*Note:* The first approach is quite similar to the algorithm for finding a four cycle in a graph in quadratic time. See here: https://sciencedirect.com/science/article/pii/S0304020808730196
Michael Wehar
CC BY-SA 4.0
2019-06-30T05:07:43.320Z
Please let me know if you find any mistakes or have any new insights.  Thank you!
Michael Wehar
CC BY-SA 4.0
2019-06-30T04:38:13.867Z
2019-07-01T01:52:47.683Z
2019-07-01T01:52:47.683Z
Michael Wehar
<p>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$). </p>

<p>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).</p>

<p>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.</p>

<p>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. <a href="https://arxiv.org/abs/1608.03245" rel="noreferrer">On the Complexity of Closest Pair via Polar-Pair of Point-Sets</a>)</p>

<p>For monochromatic Max-IP, there is an algorithm with running time $n^{2 - 1/\widetilde{O}((d/\log n)^{1/3})}$ time algorithm by <a href="https://arxiv.org/pdf/1608.04355.pdf" rel="noreferrer">Alman, Chan and Williams</a> (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.</p>

<p>Also, the approximate version of Max-IP is also studied by this paper <a href="https://eccc.weizmann.ac.il/report/2018/026/" rel="noreferrer">On The Hardness of Approximate and Exact (Bichromatic) Maximum Inner Product</a>, 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.</p>

CC BY-SA 4.0
2019-06-30T05:29:19.720Z
Does the $n^{2 - 1/\widetilde{O}((d/\log n)^{1/3})}$ time algorithm require some bounds on $d$?
Michael Wehar
CC BY-SA 4.0
2018-09-18T20:58:14.227Z
2018-09-18T21:17:26.047Z
2018-09-18T21:17:26.047Z
Lijie Chen
<p>If $k=O(\log n)$ I believe the <a href="https://arxiv.org/pdf/1608.04355.pdf" rel="noreferrer">techniques of Alman, Chan, and Williams</a> 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.)</p>

<p>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.</p>

<p>If you allow <em>approximation</em> 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. <a href="https://arxiv.org/pdf/1706.06407.pdf" rel="noreferrer">this paper</a> and its references.</p>

CC BY-SA 4.0
2018-09-18T18:57:48.477Z
2018-09-18T18:57:48.477Z
Rasmus Pagh
<p>Consider the following problems:</p>

<blockquote>
  <p><strong>Orthogonal Vectors Problem</strong></p>
  
  <p>Input: A set $S$ of $n$ Boolean vectors each of length $d$.</p>
  
  <p>Question: Do there exist distinct vectors $v_1$ and $v_2 \in S$ such that $v_1 \cdot v_2 = 0$?</p>
  
  <p><strong>Non-Orthogonal Vectors Problem</strong></p>
  
  <p>Input: A set $S$ of $n$ Boolean vectors each of length $d$ and a positive
  integer $k$.</p>
  
  <p>Question: Do there exist distinct vectors $v_1$ and $v_2 \in S$ such that $v_1 \cdot v_2 \geq k$?</p>
</blockquote>

<p>What is the relationship between these two problems?</p>

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

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

<p>(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?</p>

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

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

<blockquote>
  <p><strong>Edit:</strong> Most of the responses offer really great insights when $d$ is
  small.  </p>
  
  <p>What can be said when $d$ is larger?  Say $d = n$ or $d = \sqrt{n}$
  or at least $d = n^\alpha$ for some $\alpha &gt; 0$.</p>
</blockquote>

CC BY-SA 4.0
2018-09-17T10:20:57.960Z
Regarding (2): as far as I know, the best known algorithm for solving OVP was established in [this paper](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.711.8289&rep=rep1&type=pdf). 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](https://people.csail.mit.edu/rrw/2-csp-final.pdf).
Geoffroy Couteau
CC BY-SA 4.0
2018-09-18T11:38:03.180Z
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.
Michael Wehar
CC BY-SA 4.0
2018-09-18T11:50:43.650Z
It might even be possible to reduce the factor of $k$ to something smaller.
Michael Wehar
CC BY-SA 4.0
2018-09-18T16:59:30.247Z
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.
Ryan Williams
CC BY-SA 4.0
2018-09-18T21:44:22.667Z
@RyanWilliams Thank you very much for this point!  I'm especially interested in the case when $d$ is at least $n^\alpha$ for some $\alpha > 0$.  :)
Michael Wehar
CC BY-SA 4.0
2018-09-19T16:09:07.087Z
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)).
Rasmus Pagh
CC BY-SA 4.0
2018-09-19T16:36:20.803Z
@RasmusPagh Great point!!  Thank you very much.  :)
Michael Wehar
CC BY-SA 4.0
2018-09-19T16:52:13.463Z
@RasmusPagh I see, so with a naive version of fast rectangular matrix multiplication, we can get an algorithm running in $n^2 \cdot d^{\omega - 2}$ time.  But, based on your comment, I guess there is a trick for rectangular matrix multiplication when $d < n^{0.3}$?
Michael Wehar
CC BY-SA 4.0
2018-09-20T15:50:56.783Z
@MichaelWehar: Exactly. I think the best result is due to François Le Gall, https://arxiv.org/abs/1204.1111
Rasmus Pagh
CC BY-SA 4.0
2018-09-20T18:14:02.343Z
@RasmusPagh Thank you very much for the follow-up and the reference!!  :)
Michael Wehar
CC BY-SA 4.0
2018-09-20T18:16:48.177Z
@RasmusPagh I'm starting to wonder what happens now when $d > n$?
Michael Wehar
<cc.complexity-theory><ds.algorithms><linear-algebra><polynomial-time><boolean-matrix>
Non-Orthogonal Vectors Problem
Michael Wehar
# Non-Orthogonal Vectors Problem

(Asked by: username_0 on 2018-09-17)

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

**Tags:** cc.complexity-theory, ds.algorithms, linear-algebra, polynomial-time, boolean-matrix
> **Comments:**
> **username_1**: Regarding (2): as far as I know, the best known algorithm for solving OVP was established in [this paper](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.711.8289&rep=rep1&type=pdf). 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](https://people.csail.mit.edu/rrw/2-csp-final.pdf).  
> **username_0**: 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.  
> **username_0**: It might even be possible to reduce the factor of $k$ to something smaller.  
> **username_2**: 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.  
> **username_0**: @RyanWilliams Thank you very much for this point!  I'm especially interested in the case when $d$ is at least $n^\alpha$ for some $\alpha > 0$.  :)  
> **username_3**: 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)).  
> **username_0**: @RasmusPagh Great point!!  Thank you very much.  :)  
> **username_0**: @RasmusPagh I see, so with a naive version of fast rectangular matrix multiplication, we can get an algorithm running in $n^2 \cdot d^{\omega - 2}$ time.  But, based on your comment, I guess there is a trick for rectangular matrix multiplication when $d < n^{0.3}$?  
> **username_3**: @MichaelWehar: Exactly. I think the best result is due to François Le Gall, https://arxiv.org/abs/1204.1111  
> **username_0**: @RasmusPagh Thank you very much for the follow-up and the reference!!  :)  
> **username_0**: @RasmusPagh I'm starting to wonder what happens now when $d > n$?  

---

## 3 answers

### Answer by username_0 on 2019-06-30. Score: 1 | Accepted answer

**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.

> **Comments:**
> **username_0**: 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.  
> **username_0**: **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.  
> **username_0**: **Case 3:** When $d \leq n^{0.3}$, the third case is sometimes most efficient.  
> **username_0**: **Case 4:** When $d$ and $k$ are larger than $n$, the third approach is sometimes most efficient.  
> **username_0**: *Note:* The first approach is quite similar to the algorithm for finding a four cycle in a graph in quadratic time. See here: https://sciencedirect.com/science/article/pii/S0304020808730196  
> **username_0**: Please let me know if you find any mistakes or have any new insights.  Thank you!  

---

### Answer by username_4 on 2018-09-18. Score: 9

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](https://arxiv.org/abs/1608.03245))

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](https://arxiv.org/pdf/1608.04355.pdf) (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](https://eccc.weizmann.ac.il/report/2018/026/), 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.

> **Comments:**
> **username_0**: Does the $n^{2 - 1/\widetilde{O}((d/\log n)^{1/3})}$ time algorithm require some bounds on $d$?  

---

### Answer by username_3 on 2018-09-18. Score: 7

If $k=O(\log n)$ I believe the [techniques of Alman, Chan, and Williams](https://arxiv.org/pdf/1608.04355.pdf) 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](https://arxiv.org/pdf/1706.06407.pdf) and its references.


---

