All reports by Author Egor Klenin:

__
TR16-173
| 5th November 2016
__

Egor Klenin, Alexander Kozachinsky#### One-sided error communication complexity of Gap Hamming Distance

Revisions: 2

Egor Klenin, Alexander Kozachinsky

Assume that Alice has a binary string $x$ and Bob a binary string $y$, both of length $n$. Their goal is to output 0, if $x$ and $y$ are at least $L$-close in Hamming distance, and output 1, if $x$ and $y$ are at least $U$-far in Hamming distance, where ... more >>>