An Equivalence Class for Orthogonal Vectors

The Orthogonal Vectors problem (textsfOV) asks: given n vectors in 0,1O(log n), are two of them orthogonal? textsfOV is easily solved in O(n2 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 textsfOV cannot be solved in (say) n1.99 time. However, unlike the APSP problem, few other problems are known to be non-trivially equivalent to textsfOV. We show textsfOV is truly-subquadratic equivalent to several fundamental problems, all of which (a priori) look harder than textsfOV. A partial list is given below: (textsfMin-IP/textsfMax-IP) Find a red-blue pair of vectors with minimum (respectively, maximum) inner product, among n vectors in 0,1O(log n). (textsfExact-IP) Find a red-blue pair of vectors with inner product equal to a given target integer, among n vectors in 0,1O(log n). (textsfApx-Min-IP/textsfApx-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,1O(log n). (Approx. textsfBichrom.-ℓp-Closest-Pair) Compute a (1 + Omega(1))-approximation to the ℓp-closest red-blue pair (for a constant p ∈ [1,2]), among n points in ℝd, d ≤ no(1). (Approx. textsfℓp-Furthest-Pair) Compute a (1 + Omega(1))-approximation to the ℓp-furthest pair (for a constant p ∈ [1,2]), among n points in ℝd, d ≤ no(1). We also show that there is a poly(n) space, n1-ε query time data structure for Partial Match with vectors from 0,1O(log n) if and only if such a data structure exists for 1+Omega(1) Approximate Nearest Neighbor Search in Euclidean space.