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.
