OV

Description

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

Related Problems

Generalizations: k-OV

Subproblem: Unbalanced OV

Related: 3-OV

Parameters

$n$: number of vectors

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

Table of Algorithms

Name	Year	Time	Space	Approximation Factor	Model	Reference
Exhaustive search	-	$O(d*n^k)$	$O(k)$ auxiliary	Exact	Deterministic
Abboud, Williams, Yu	2015	$O(n^{({2}-{1}/O(d/log(n)))})$		Exact	Randomized	Time
Reduction to Abboud, Williams, Yu	2015	$O(n^{(k-{1}/O(d/log(n)))})$		Exact	Randomized	Time
Chan, Williams	2016	$O(n^{({2}-{1}/O(d/log(n)))})$		Exact	Deterministic	Time
Reduction to Chan, Williams	2016	$O(n^{(k-{1}/O(d/log(n)))})$		Exact	Deterministic	Time

Reductions TO Problem

Problem	Implication	Year	Citation	Reduction
Diameter 2 vs 3	If: to-time: $O(N^{({2}-\epsilon)})$ where $N = nd$ and $V,E = O(n)$ Then: from-time: $O((nd)^{({2}-\epsilon)}) \leq n^{({2}-\epsilon)} poly(d)$ where {2} sets of $n$ $d$-dimensional vectors	2013	https://people.csail.mit.edu/virgi/diam.pdf	link
Edit Distance	If: to-time: $O(n^{({2}-\epsilon)})$ where $n$ is length of sequence Then: from-time: $O(d^{O({1})}*(N)^{({2}-\epsilon)})$ where ${2}$ sets of $n$ $d$-dimensional vectors	2014	https://arxiv.org/pdf/1412.0348.pdf	link
Partial Match	If: to-time: $n^{2-\epsilon}*poly(d)$ for some $\epsilon > {0}$ Then: from-time: $n^{2-\epsilon'}*poly(d)$ for some $\epsilon' > {0}$	2020	https://people.csail.mit.edu/virgi/6.s078/lecture6-post.txt	link
Bichromatic Hamming Close Pair	assume: OVH then: there is no algorithm to solve target in time $O({2}^{o(d)}n^{2-\epsilon})$ on a set of $n$ points in $\{0,{1}\}^{c\log n}$	2015	https://ieeexplore.ieee.org/abstract/document/7354392	link
Subtree Isomorphism	assume: OVH then: for all $d \geq {2}$, target on two rooted unordered trees of size $O(n)$, degree $d$, and height $h \leq {2}\log_d n + O(\log \log n)$ cannot be solved in truly subquadratic $O(n^{2-\epsilon})$ time	2018	https://dl.acm.org/doi/pdf/10.1145/3093239	link
Largest Common Subtree	assume: OVH then: for all constants $d \geq {2}$, target on two rooted trees of size at most $n$, degree $d$, and height $h \leq \log_d n + O(\log \log n)$ cannot be solved in truly subquadtratic $O(n^{2-\epsilon})$ time	2018	https://dl.acm.org/doi/pdf/10.1145/3093239	link
Generalized Büchi Games	assume: OVH then: there is no $O(m^{2-\epsilon})$ or $O(\min_{1 \leq i \leq k} b_i \cdot (k \cdot m)^{1-\epsilon})$-time algorithm (for any $\epsilon > {0}$ for generalized Büchi games. In particular there is no such algorithm for deciding whether the winning set is non-empty or deciding whether a specifc vertex is in the winning set.	2016	https://arxiv.org/pdf/1607.05850.pdf	link
Disjunctive Reachability Queries in MDPs	assume: Strong Triangle then: there is no $O(m^{2-\epsilon})$ or $O((k \cdot m)^{1-\epsilon})$ algorithm, for any $\epsilon > {0}$ for target.	2016	https://dl.acm.org/doi/pdf/10.1145/2933575.2935304	link
Disjunctive Queries of Safety in Graphs	assume: OVH then: there is no $O(m^{2-\epsilon})$ or $O((k \cdot m)^{1 - \epsilon})$ algorithm for any $\epsilon > {0}$ for disjunctive safety ovjectives/queries in MDPs.	2016	https://dl.acm.org/doi/pdf/10.1145/2933575.2935304	link
k-OV	OV is a strict subproblem of k-OV			link

Reductions FROM Problem

Problem	Implication	Year	Citation	Reduction
Partial Match	If: to-time: $n^{2-\epsilon}*poly(d)$ for some $\epsilon > {0}$ Then: from-time: $n^{2-\epsilon'}*poly(d)$ for some $\epsilon' > {0}$	2020	https://people.csail.mit.edu/virgi/6.s078/lecture6-post.txt	link

References/Citation

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