k-OV (Orthogonal Vectors)
Jump to navigation
Jump to search
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
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 | link | |||
3-OV | link |