Unbalanced OV (Orthogonal Vectors)

From Algorithm Wiki
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

Related: k-OV, 3-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