# Unbalanced OV (Orthogonal Vectors)

(Redirected from UOV)

Jump to navigation
Jump to search
## 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 |