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	2005		link
OV	OV is a strict subproblem of k-OV			link
3-OV	{3}-OV is a strict subproblem of k-OV			link

References/Citation

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