(\(\Leftarrow \)) Suppose \(\mathcal A\) solves bichromatic \(\mathsf{OV}_{n,\ell }\) in \(O(n^{2-\varepsilon }\operatorname {poly}(\ell ))\). Given an \(\mathsf{OV}_{n,\ell }\) instance \(V = \{ v_1, \ldots , v_n\} \), first check (in time \(O(n\ell )\)) whether any \(v_i\) is the all-zero vector; if so, this is a yes instance. Otherwise set \(A = B = V\) and run \(\mathcal A\) on \(A,B\). Since no vector is zero, \(\langle v_i, v_i \rangle \ne 0\) for all \(i\), so a pair \(i \ne j\) with \(\langle v_i, v_j \rangle = 0\) exists iff \(\mathcal A\) reports an orthogonal pair \(a \in A\), \(b \in B\). Total time \(O(n^{2-\varepsilon }\operatorname {poly}(\ell ) + n\ell ) = O(n^{2-\varepsilon }\operatorname {poly}(\ell ))\).

(\(\Rightarrow \)) Suppose \(\mathcal A'\) solves \(\mathsf{OV}_{n,\ell }\) in \(O(n^{2-\varepsilon }\operatorname {poly}(\ell ))\). Given a bichromatic instance \(A = \{ a_1, \ldots , a_n\} \), \(B = \{ b_1, \ldots , b_n\} \) with \(a_i, b_j \in \{ 0,1\} ^{\ell }\), build \(a_i' = (a_i, 1, 0) \in \mathbb {R}^{\ell +2}\) and \(b_j' = (b_j, 0, 1) \in \mathbb {R}^{\ell +2}\), and let \(A' = \{ a_1', \ldots , a_n'\} \), \(B' = \{ b_1', \ldots , b_n'\} \). Then \(\langle a_i', a_j' \rangle \ge 1\) and \(\langle b_i', b_j' \rangle \ge 1\) for all \(i,j\) (the appended coordinates contribute \(1\)), while \(\langle a_i', b_j' \rangle = \langle a_i, b_j \rangle \). Hence a pair of orthogonal vectors in \(A' \cup B'\) can only be of the form \(a_i', b_j'\), i.e. an orthogonal bichromatic pair \(a_i, b_j\). Running \(\mathcal A'\) on \(A' \cup B'\) (of size \(2n\) in dimension \(\ell +2\)) decides the bichromatic instance in time \(O((2n)^{2-\varepsilon }\operatorname {poly}(\ell +2)) = O(n^{2-\varepsilon }\operatorname {poly}(\ell ))\).

Given an \(\mathsf{OV}_{n,\ell }\) instance, run the (approximate) Min-IP algorithm to obtain a pair achieving the minimum inner product (or a \(\gamma \)-approximation of it) and test whether that value is \(0\). There is an orthogonal pair iff the minimum inner product is \(0\); and any multiplicative \(\gamma \)-approximation of \(0\) must itself be \(0\), so the \(\gamma \)-approximate version detects it too. Hence a truly subquadratic algorithm for (\(\gamma \)-)Min-IP gives one for OV, which is impossible under OVC (Conjecture 24).

Given a \(\mathsf{Min\text{-}IP}_{n,\ell }\) instance \(V = \{ v_1, \ldots , v_n\} \), partition \(V\) into two halves \(V_1, V_2\) of equal size and run \(\mathcal A\) on the bichromatic instance \((V_1, V_2)\); this returns the minimal pair with one element in each half. Then recurse: split \(V_1\) into two equal halves and find the minimal pair inside \(V_1 \times V_1\), and likewise for \(V_2\). The minimal pair of the whole instance lies either across the top-level split or inside one half, so it is found by some recursive call. The running time satisfies

for some \(\varepsilon '{\gt}0\) (the geometric sum is dominated by its first term). The same argument applies to \(\gamma \text{-}\mathsf{Min\text{-}IP}\) (the optimal pair still appears in some recursive call) and to \(\mathsf{Min\text{-}IP}_{n,\ell ,t}\) (we examine all pairs across some call).

Identical to the proof of Lemma 36: split the input recursively into halves and run the bichromatic Max-IP algorithm \(\mathcal A\) on each pair of halves; the maximal pair appears in some recursive call, and the geometric sum of running times is dominated by the top term, giving \(O(n^{2-\varepsilon '}\operatorname {poly}(\ell ))\).

Given an \(\mathsf{OV}_{n,\ell }\) instance \(v_1, \ldots , v_n \in \{ 0,1\} ^{\ell }\), partition the vectors into subsets \(S_1, \ldots , S_{\ell }\) where \(S_j\) contains all vectors with exactly \(j\) ones. For each pair \(1 \le i,j \le \ell \) let \(\bar S_j\) consist of the vectors in \(S_j\) with all entries flipped. Then for any \(v \in S_i\) and \(w \in \bar S_j\) (so \(w = \bar u\) with \(u \in S_j\)), we have \(\langle v, w \rangle = i - \langle v, u \rangle \), hence \(\langle v, \bar u \rangle = i\) iff \(\langle v, u \rangle = 0\). Therefore running the bichromatic Max-IP algorithm \(\mathcal A\) on \((S_i, \bar S_j)\) and testing whether the maximum inner product equals \(i\) reveals whether there is an orthogonal pair with one vector in \(S_i\) and one in \(S_j\). Doing this for all \(\ell ^2\) pairs decides OV. The total time is \(O(\ell ^{2}\cdot n^{2-\varepsilon }\operatorname {poly}(\ell )) = O(n^{2-\varepsilon }\operatorname {poly}(\ell ))\).