Orthogonal Vectors Hypothesis (OVH)

From Algorithm Wiki
Jump to navigation Jump to search

Target Problem

OV

Description

For no $\epsilon > 0$ there is an algorithm for OV, restricted to $n = m$, that runs in time $O(n^{(2−\epsilon)}poly(d))$.

Implies the following Hypothesis

SETH, UOVH

Implied by the following Hypothesis

k-OV Hypothesis, UOVH

Computation Model

Proven?

No

Year

References/Citation

https://arxiv.org/pdf/1502.01063.pdf

Retrieved from "https://algorithm-wiki.csail.mit.edu/w/index.php?title=Orthogonal_Vectors_Hypothesis_(OVH)&oldid=44333"