Orthogonal Vectors Hypothesis (OVH)
Revision as of 11:30, 15 February 2023 by Admin (talk | contribs) (Created page with "== 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 == Compu...")
Target Problem
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
Implied by the following Hypothesis
Computation Model
Proven?
No