# 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 | OV is a strict subproblem of k-OV | link | ||

3-OV | {3}-OV is a strict subproblem of k-OV | link |