An Equivalence Class for Orthogonal Vectors

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