Non-Orthogonal Vectors Problem 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 &gt; 0$.
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.