# An Equivalence Class for Orthogonal Vectors

arXiv: https://arxiv.org/abs/1811.12017 · HTML: https://mlsanity.com/paper/1811.12017/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Nov 2018.

## Built on by (most cited first, 5 of 5)

- [Computational Limits of Low-Rank Adaptation (LoRA) Fine-Tuning for Transformer Models](https://mlsanity.com/paper/2406.03136/) (2024)
- [Bypass Exponential Time Preprocessing: Fast Neural Network Training via Weight-Data Correlation Preprocessing](https://mlsanity.com/paper/2211.14227/) (2022)
- [Sublinear Least-Squares Value Iteration via Locality Sensitive Hashing](https://mlsanity.com/paper/2105.08285/) (2021)
- [Hardness of Low Rank Approximation of Entrywise Transformed Matrix Products](https://mlsanity.com/paper/2311.01960/) (2023)
- [Resource Constrained Pathfinding with A* and Negative Weights](https://mlsanity.com/paper/2503.11037/) (2025)

## Abstract (arXiv)

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.