3-OV: Difference between revisions
Jump to navigation
Jump to search
(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...") |
No edit summary |
||
| (One intermediate revision by the same user not shown) | |||
| Line 12: | Line 12: | ||
== Parameters == | == Parameters == | ||
$n$: number of vectors per set | |||
$d$: dimension of each vector; $d = omega(log(n))$ | |||
$d$: dimension of each vector; $d = omega(log(n))$ | |||
== Table of Algorithms == | == Table of Algorithms == | ||
| Line 29: | Line 30: | ||
| [[Diameter 3 vs 7]] || style="text-align:left;" | If: to-time: $O(N^{({3}/{2}-\epsilon)}$ where $N=n^{2} d^{2}$ and $\epsilon > {0}$<br/>Then: from-time: $n^{3-{2}\epsilon} poly(d)$ || 2018 || https://dl.acm.org/doi/pdf/10.1145/3188745.3188950 || [[Reduction from 3-OV to Diameter 3 vs 7|link]] | | [[Diameter 3 vs 7]] || style="text-align:left;" | If: to-time: $O(N^{({3}/{2}-\epsilon)}$ where $N=n^{2} d^{2}$ and $\epsilon > {0}$<br/>Then: from-time: $n^{3-{2}\epsilon} poly(d)$ || 2018 || https://dl.acm.org/doi/pdf/10.1145/3188745.3188950 || [[Reduction from 3-OV to Diameter 3 vs 7|link]] | ||
|- | |- | ||
| [[k-OV]] || style="text-align:left;" | | | [[k-OV]] || style="text-align:left;" | {3}-OV is a strict subproblem of k-OV || || || [[Reduction from 3-OV to k-OV|link]] | ||
|- | |- | ||
|} | |} | ||
Latest revision as of 14:48, 15 February 2023
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 | {3}-OV is a strict subproblem of k-OV | link |