OV (Orthogonal Vectors)

From Algorithm Wiki
(Redirected from 2-OV)
Jump to navigation Jump to search

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