Bichromatic Hamming Close Pair (Bichromatic Hamming Close Pair)

From Algorithm Wiki
(Redirected from BHCP)
Jump to navigation Jump to search

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