Unbalanced Orthogonal Vectors Hypothesis (UOVH)

Target Problem

UOV

Description

Let $0 < \alpha \leq 1$. For no $\epsilon > 0$ there is an algorithm for OV, restricted to $m = \Theta(n^\alpha)$ and $d \leq n^{o(1)}$, that runs in time $O((nm)^{(1−\epsilon)})$.

Implies the following Hypothesis

SETH, OVH

Implied by the following Hypothesis

OVH

Proven?

No

References/Citation

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