Unbalanced OV: Difference between revisions
Jump to navigation
Jump to search
(Created page with "{{DISPLAYTITLE:Unbalanced OV (Orthogonal Vectors)}} == Description == Let $0 < \alpha \leq 1$. UOV is the OV problem with the specifications that $A$ is of size $n$ and $B$ is of size $m=\Theta(n^\alpha)$ and $d\leq n^{o(1)}$. == Related Problems == Generalizations: OV Related: k-OV, 3-OV == Parameters == <pre>$n$: size of $A$ $m$: size of $B$ $d$: dimensionality of vectors</pre> == Table of Algorithms == Currently no algorithms in our database fo...") |
No edit summary |
||
| Line 12: | Line 12: | ||
== Parameters == | == Parameters == | ||
$n$: size of $A$ | |||
$m$: size of $B$ | $m$: size of $B$ | ||
$d$: dimensionality of vectors | |||
$d$: dimensionality of vectors | |||
== Table of Algorithms == | == Table of Algorithms == | ||
Latest revision as of 12:03, 15 February 2023
Description
Let $0 < \alpha \leq 1$. UOV is the OV problem with the specifications that $A$ is of size $n$ and $B$ is of size $m=\Theta(n^\alpha)$ and $d\leq n^{o(1)}$.
Related Problems
Generalizations: OV
Parameters
$n$: size of $A$
$m$: size of $B$
$d$: dimensionality of vectors
Table of Algorithms
Currently no algorithms in our database for the given problem.
Reductions TO Problem
| Problem | Implication | Year | Citation | Reduction |
|---|---|---|---|---|
| Dynamic Time Warping | If: to-time: $O((nm)^{({1}-\epsilon)})$, where $|x| = O(nd)$ and $|y| = O(md)$ Then: from-time: $O((nm)^{({1}-\epsilon/{2})})$ |
2015 | https://arxiv.org/pdf/1502.01063.pdf | link |
| Longest Common Subsequence | If: to-time: $O((nm)^{({1}-\epsilon)})$, where $|x| = O(nd)$ and $|y| = O(md)$ Then: from-time: $O((nm)^{({1}-\epsilon/{2})})$ |
2015 | https://arxiv.org/pdf/1502.01063.pdf | link |