k-OV (Orthogonal Vectors)

Description

Given $k$ sets of $d$-dimensional vectors $A_1, A_2, \ldots, A_k$, each of size $n$, does there exist $a_1 \in A_1, a_2 \in A_2, \ldots, a_k \in A_k$ such that $a_1 * a_2 * \ldots * a_k = 0$?

Related Problems

Subproblem: OV, 3-OV

Related: 3-OV, Unbalanced OV

Parameters

$n$: number of vectors per set

$k$: number of sets

$d$: dimension of each vector; $d = omega(log(n))$

Table of Algorithms

Name Year Time Space Approximation Factor Model Reference
Exhaustive search - $O(d*n^k)$ $O(k)$ auxiliary Exact Deterministic
Reduction to Abboud, Williams, Yu 2015 $O(n^{(k-{1}/O(d/log(n)))})$ Exact Randomized Time
Reduction to Chan, Williams 2016 $O(n^{(k-{1}/O(d/log(n)))})$ Exact Deterministic Time

Reductions FROM Problem

Problem Implication Year Citation Reduction
CNF-SAT If: to-time: $N^{(k-\epsilon)} poly(m)$ where $m$-dimensional vectors, $k$-OV, $N$ vectors per set
Then: from-time: ${2}^{(n-\epsilon')} \poly(m)$ where $\epsilon' = \epsilon/k > {0}$, $n$ variables, $m$ clauses