Orthogonal Vectors Hypothesis (OVH)

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

Proven?

No

References/Citation

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