An equivalence class for orthogonal vectors

DOI10.1137/1.9781611975482.2MaRDI QIDQ5236183zbMATH OpenOpenAlexFDO

Authors Lijie Chen, Ryan Williams

Publication date 15 October 2019

Published in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Data structures (68P05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)

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.

Recommendations

• On the hardness of approximate and exact (bichromatic) maximum inner product
• scientific article; zbMATH DE number 7250154
• Orthogonal vectors indexing
• Finding orthogonal vectors in discrete structures
• Finding a vector orthogonal to roughly half a collection of vectors

Cited in

(20)

• The fine-grained complexity of multi-dimensional ordering properties
• Are orthogonal separable coordinates really classified?
• scientific article; zbMATH DE number 3887878 (Why is no real title available?)
• Hardness of bichromatic closest pair with Jaccard similarity
• On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic
• The Orthogonal Vectors Conjecture for Branching Programs and Formulas
• scientific article; zbMATH DE number 7561744 (Why is no real title available?)
• Orthogonal vectors indexing
• On the hardness of approximate and exact (bichromatic) maximum inner product
• Finding orthogonal vectors in discrete structures
• The Fine-Grained Complexity of Median and Center String Problems Under Edit Distance
• Improved Merlin-Arthur protocols for central problems in fine-grained complexity
• Finer-grained reductions in fine-grained hardness of approximation
• Finer-grained reductions in fine-grained hardness of approximation
• Depth-3 circuit lower bounds for k-OV
• Tensor ranks and the fine-grained complexity of dynamic programming
• Fine-grained hardness for edit distance to a fixed sequence
• Counting short vector pairs by inner product and relations to the permanent
• Non-Boolean OMv: one more reason to believe lower bounds for dynamic problems
• The planted orthogonal vectors problem

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)