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

$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

References/Citation

https://epubs.siam.org/doi/abs/10.1137/1.9781611974331.ch87