Bichromatic Hamming Close Pair

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.ezproxy.canberra.edu.au/abstract/document/7354392	link