The Orthogonal Vectors problem ($\textsf{ OV}$) asks: given $n$ vectors in $\{ 0,1\}^{ O(\log n)}$, are two of them orthogonal? $\textsf{ OV}$ is easily solved in $O(n^2 \log n)$ time, and it is a central problem in fine-grained complexity: dozens of conditional lower bounds are based on the popular hypothesis that $\textsf{ OV}$ cannot be solved in (say) $n^{ 1.99}$ time. However, unlike the APSP problem, few other problems are known to be non-trivially equivalent to $\textsf{ OV}$. We show $\textsf{ OV}$ is truly-subquadratic equivalent to several fundamental problems, all of which (a priori) look harder than $\textsf{ OV}$. A partial list is given below: ($\textsf{ Min-IP}/\textsf{ Max-IP}$) Find a red-blue pair of vectors with minimum (respectively, maximum) inner product, among $n$ vectors in $\{ 0,1\}^{ O(\log n)}$. ($\textsf{ Exact-IP}$) Find a red-blue pair of vectors with inner product equal to a given target integer, among $n$ vectors in $\{ 0,1\}^{ O(\log n)}$. ($\textsf{ Apx-Min-IP}/\textsf{ Apx-Max-IP}$) Find a red-blue pair of vectors that is a 100-approximation to the minimum (resp. maximum) inner product, among $n$ vectors in $\{ 0,1\}^{ O(\log n)}$. (Approx. $\textsf{ Bichrom.-$\ell_p$-Closest-Pair}$) Compute a $(1 + \Omega(1))$-approximation to the $\ell_p$-closest red-blue pair (for a constant $p \in [1,2]$), among $n$ points in $\mathbb{ R}^d$, $d \le n^{ o(1)}$. (Approx. $\textsf{ $\ell_p$-Furthest-Pair}$) Compute a $(1 + \Omega(1))$-approximation to the $\ell_p$-furthest pair (for a constant $p \in [1,2]$), among $n$ points in $\mathbb{ R}^d$, $d \le n^{ o(1)}$. We also show that there is a $\text{ poly}(n)$ space, $n^{ 1-\epsilon}$ query time data structure for Partial Match with vectors from $\{ 0,1\}^{ O(\log n)}$ if and only if such a data structure exists for $1+\Omega(1)$ Approximate Nearest Neighbor Search in Euclidean space.
Categories: cs.DS