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

$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