  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.
