An Equivalence Class for Orthogonal Vectors

DOI10.1137/1.9781611975482.2zbMATH Open1431.68046arXiv1811.12017OpenAlexW2951440907MaRDI QIDQ5236183

Author name not available (Why is that?)

Publication date: 15 October 2019

Published in: (Search for Journal in Brave)

Abstract: The Orthogonal Vectors problem ($extsfOV$) asks: given $n$ vectors in ${0,1}^{O(logn)}$, are two of them orthogonal? $extsfOV$ is easily solved in $O(n^{2}logn)$ time, and it is a central problem in fine-grained complexity: dozens of conditional lower bounds are based on the popular hypothesis that $extsfOV$ 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 $extsfOV$. We show $extsfOV$ is truly-subquadratic equivalent to several fundamental problems, all of which (a priori) look harder than $extsfOV$. A partial list is given below: ($extsfMin-IP/extsfMax-IP$) Find a red-blue pair of vectors with minimum (respectively, maximum) inner product, among $n$ vectors in ${0,1}^{O(logn)}$. ($extsfExact-IP$) Find a red-blue pair of vectors with inner product equal to a given target integer, among $n$ vectors in ${0,1}^{O(logn)}$. ($extsfApx-Min-IP/extsfApx-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(logn)}$. (Approx. $$ell_p$$) Compute a $(1+Omega(1))$-approximation to the $el{l}_p$-closest red-blue pair (for a constant $pin[1,2]$), among $n$ points in $mathbb{R}^d$, $dle{n}^{o(1)}$. (Approx. $$ell_p$$) Compute a $(1+Omega(1))$-approximation to the $el{l}_p$-furthest pair (for a constant $pin[1,2]$), among $n$ points in $mathbb{R}^d$, $dle{n}^{o(1)}$. We also show that there is a $extpoly(n)$ space, $n^{1-epsilon}$ query time data structure for Partial Match with vectors from ${0,1}^{O(logn)}$ if and only if such a data structure exists for $1+Omega(1)$ Approximate Nearest Neighbor Search in Euclidean space.

Full work available at URL: https://arxiv.org/abs/1811.12017

Mathematics Subject Classification ID

No records found.

This page was built for publication: An Equivalence Class for Orthogonal Vectors

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5236183)