OV

Given $n$ vectors in $\{0,1\}^{O(\log n)}$ , are two of them orthogonal

Parameters

$n$ : number of vectors
$d$ : dimension of each vector; $d = O(log(n))$ typically

Related Problems

k-OV1
- 3-OV

Filters

Computational Model

Randomization

Approximation

Algorithms Table

Displaying 2 of 2 algorithms

				See more
Chan, Williams	2016	$O(n^{(2-1/O(d/log(n)))})$
Abboud, Williams, Yu	2015	$O(n^{(2-1/O(d/log(n)))})$

Reductions Table

Displaying 18 of 18 reductions

Other relevant algorithms

Insuffient Data to display table