3-OV (Orthogonal Vectors)

From Algorithm Wiki
Revision as of 15:48, 15 February 2023 by Admin (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search


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


$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