Bichromatic Hamming Close Pair: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
Line 6: | Line 6: | ||
== Parameters == | == Parameters == | ||
n: number of binary vectors in each set | $n$: number of binary vectors in each set | ||
d: dimensionality of vectors | $d$: dimensionality of vectors | ||
t: max Hamming distance | $t$: max Hamming distance | ||
== Table of Algorithms == | == Table of Algorithms == |
Latest revision as of 08:28, 10 April 2023
Description
Given two sets $A = \{a_1, \ldots, a_n\} \subseteq \{0, 1\}^d$ and $B = \{b_1, \ldots, b_n\} \subseteq \{0, 1\}^d$ of $n$ binary vectors and an integer $t \in \{2, \ldots, d\}$, decide if there exists a pair $a \in A$ and $b \in B$ such that the number of coordinates in which they differ is less than $t$ (formally, $Hamming(a, b) := |a − b|1 < t$). If there is such a pair $(a, b)$, we call it a close pair.
Parameters
$n$: number of binary vectors in each set
$d$: dimensionality of vectors
$t$: max Hamming distance
Table of Algorithms
Currently no algorithms in our database for the given problem.
Reductions TO Problem
Problem | Implication | Year | Citation | Reduction |
---|---|---|---|---|
Approximate Hard-Margin SVM | assume: SETH then: let $k(a,a')$ be the Gaussian kernel with $C={100}\log n$ and let $\epsilon = \exp(-\omega(\log^{2} n))$, then approximating the optimal value of target within multiplicative factor ${1}+\epsilon$ requires almost quadratic time. |
2017 | https://proceedings.neurips.cc/paper/2017/file/635440afdfc39fe37995fed127d7df4f-Paper.pdf | link |
Reductions FROM Problem
Problem | Implication | Year | Citation | Reduction |
---|---|---|---|---|
OV | 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 |