# 3-OV (Orthogonal Vectors)

Jump to navigation
Jump to search

## 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 |