2015/11/27 by Alexander Kozachinskiy, Kozachinskiy, Alexander
Computer Science · #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Cryptography and Data Security #FOS: Computer and information sciences #Optimization and Search Problems #cs.CC
paper · pdf · doi:10.48550/arxiv.1511.08854
openalex publication_date 2015/11/27 · arxiv created 2015/12/01 · arxiv updated 2015/12/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper we obtain some bounds on communication complexity of Gap Hamming Distance problem (GHDnL, U): Alice and Bob are given binary string of length n and they are guaranteed that Hamming distance between their inputs is either ≤ L or ≥ U for some L < U. They have to output 0, if the first inequality holds, and 1, if the second inequality holds. In this paper we study the communication complexity of GHDnL, U for probabilistic protocols with one-sided error and for deterministic protocols. Our first result is a protocol which communicates O(((s)/(U))^(1)/(3) ⋅ nlog n) bits and has one-sided error probability e-s provided s ≥ ((L + (10)/(n))3)/(U2). Our second result is about deterministic communication complexity of GHDn0, t. Surprisingly, it can be computed with logarithmic precision: D(GHDn0, t) = n - log2 V2(n, \lfloor(t)/(2)\rfloor) + O(log n), where V2(n, r) denotes the size of Hamming ball of radius r. As an application of this result for every c < 2 we prove a Ω((n(2 - c)2)/(p)) lower bound on the space complexity of any c-approximate deterministic p-pass streaming algorithm for computing the number of distinct elements in a data stream of length n with tokens drawn from the universe U = \1, 2, …, n\. Previously that lower bound was known for c < (3)/(2) and for c < 2 but with larger |U|.