OV (Orthogonal Vectors)
(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 |