期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2016
卷号：2016
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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 L U are some integer parameters known to both parties. If the Hamming distance between x and y lies in the interval ( L U ) , they are allowed to output anything. This problem is called the Gap Hamming Distance. In this paper we study public-coin one-sided error communication complexity of this problem. The error with probability at most 1/2 is allowed only for pairs at Hamming distance at least U . In this paper we establish lower bound ( L 2 U ) for this complexity. The main result of the paper is the simultaneous protocol communicating O (( L 2 U ) log L ) bits. Its complexity differs from the lower bound only by a O ( log L ) factor.
