3-OV (Orthogonal Vectors)
Revision as of 10:27, 15 February 2023 by Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:3-OV (Orthogonal Vectors)}} == Description == Given 3 sets of $d$-dimensional vectors $A_1, A_2, A_3$, each of size $n$, does there exist $a_1 \in A_1, a_2 \in A_2, a_3 \in A_3$ such that $a_1 * a_2 * a_3 = 0$? == Related Problems == Generalizations: k-OV Related: OV, Unbalanced OV == Parameters == <pre>$n$: number of vectors per set $d$: dimension of each vector; $d = omega(log(n))$</pre> == Table of Algorithms == Currently no algo...")
Description
Given 3 sets of $d$-dimensional vectors $A_1, A_2, A_3$, each of size $n$, does there exist $a_1 \in A_1, a_2 \in A_2, a_3 \in A_3$ such that $a_1 * a_2 * a_3 = 0$?
Related Problems
Generalizations: k-OV
Related: OV, Unbalanced OV
Parameters
$n$: number of vectors per set $d$: dimension of each vector; $d = omega(log(n))$
Table of Algorithms
Currently no algorithms in our database for the given problem.
Reductions TO Problem
| Problem | Implication | Year | Citation | Reduction |
|---|---|---|---|---|
| Diameter 3 vs 7 | If: to-time: $O(N^{({3}/{2}-\epsilon)}$ where $N=n^{2} d^{2}$ and $\epsilon > {0}$ Then: from-time: $n^{3-{2}\epsilon} poly(d)$ |
2018 | https://dl.acm.org/doi/pdf/10.1145/3188745.3188950 | link |
| k-OV | link |