k-OV

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$

Parameters

$n$ : number of vectors per set
$k$ : number of sets
$d$ : dimension of each vector; $d = omega(log(n))$

Filters

Computational Model

Randomization

Approximation

Algorithms Table

Displaying 3 of 3 algorithms


Reduction to Chan, Williams	2016	$O(n^{(k-1/O(d/log(n)))})$
Reduction to Abboud, Williams, Yu	2015	$O(n^{(k-1/O(d/log(n)))})$
Exhaustive search	-	$O(d*n^k)$	O(k) auxiliary

Reductions Table

Displaying 3 of 3 reductions


k-OV	Diameter k vs 2k-1	2021
Conjunctive Normal Form SAT	k-OV	2005
OV	k-OV

Other relevant algorithms

Insuffient Data to display table