Alice and Bob want to know if two strings of length n are almost equal. That is, do the strings differ on at most a bits? Let 0 ⩽ a ⩽ n − 1. We show (1) any deterministic protocol—as well as any error-free quantum protocol ( C * version)—for this problem requires at least n − 2 bits of communication, and (2) a lower bound of n /2 − 1 for error-free Q * quantum protocols. We also show the same results for determining if two strings differ in exactly a bits. Our results are obtained by lower-bounding the ranks of the appropriate matrices.
Alice and Bob want to know if two strings of length n are almost equal. That is, do the strings differ on at most a bits? Let 0 ⩽ a ⩽ n − 1. We show (1) any deterministic protocol—as well as any error-free quantum protocol ( C * version)—for this problem requires at least n − 2 bits of communication, and (2) a lower bound of n /2 − 1 for error-free Q * quantum protocols. We also show the same results for determining if two strings differ in exactly a bits. Our results are obtained by lower-bounding the ranks of the appropriate matrices.
In this paper we obtain some bounds on communication complexity of Gap Hamming Distance problem (GHDL,Un): 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 GHDL,Un for probabilistic protocols with one-sided error and for deterministic protocols. Our first result is a protocol which communicates O((Us)31⋅nlogn) bits and has one-sided error probability e−s provided s≥U2(L+n10)3. Our second result is about deterministic communication complexity of GHD0,tn. Surprisingly, it can be computed with logarithmic precision: D(GHD0,tn)=n−log2V2(n,⌊2t⌋)+O(logn), 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 Ω(pn(2−c)2) 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<23 and for c<2 but with larger ∣U∣.
Assume that Alice has a binary string x and Bob a binary string y, both strings are 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 determine this complexity up to factors logarithmic in L. The protocol we construct for the upper bound is simultaneous.
We study the communication complexity of a number of graph properties where the edges of the graph G are distributed between Alice and Bob (i.e., each receives some of the edges as input). Our main results are: * An Omega(n) lower bound on the quantum communication complexity of deciding whether an n-vertex graph G is connected, nearly matching the trivial classical upper bound of O(n log n) bits of communication. * A deterministic upper bound of O(n^{3/2}log n) bits for deciding if a bipartite graph contains a perfect matching, and a quantum lower bound of Omega(n) for this problem. * A Theta(n^2) bound for the randomized communication complexity of deciding if a graph has an Eulerian tour, and a Theta(n^{3/2}) bound for the quantum communication complexity of this problem. The first two quantum lower bounds are obtained by exhibiting a reduction from the n-bit Inner Product problem to these graph problems, which solves an open question of Babai, Frankl and Simon. The third quantum lower bound comes from recent results about the quantum communication complexity of composed functions. We also obtain essentially tight bounds for the quantum communication complexity of a few other problems, such as deciding if G is triangle-free, or if G is bipartite, as well as computing the determinant of a distributed matrix.
After Bob sends Alice a bit, she responds with a lengthy reply. At the cost of a factor of two in the total communication, Alice could just as well have given Bob her two possible replies at once without listening to him at all, and have him select which one applies. Motivated by a conjecture stating that this form of “round elimination” is impossible in exact quantum communication complexity, we study the orthogonal rank and a symmetric variant thereof for a certain family of Cayley graphs. The orthogonal rank of a graph is the smallest number d for which one can label each vertex with a nonzero d-dimensional complex vector such that adjacent vertices receive orthogonal vectors. We show an exp(n) lower bound on the orthogonal rank of the graph on {0, 1} n in which two strings are adjacent if they have Hamming distance at least n/2. In combination with previous work, this implies an affirmative answer to the above conjecture.
We show that almost all known lower bound methods for communication complexity are also lower bounds for the information complexity. In particular, we define a relaxed version of the partition bound of Jain and Klauck and prove that it lower bounds the information complexity of any function. Our relaxed partition bound subsumes all norm based methods (e.g. the γ2 method) and rectangle-based methods (e.g. the rectangle/corruption bound, the smooth rectangle bound, and the discrepancy bound), except the partition bound. Our result uses a new connection between rectangles and zero-communication protocols where the players can either output a value or abort. We prove the following compression lemma: given a protocol for a function f with information complexity I, one can construct a zero-communication protocol that has non-abort probability at least 2-O(I)and that computes f correctly with high probability conditioned on not aborting. Then, we show how such a zero-communication protocol relates to the relaxed partition bound. We use our main theorem to resolve three of the open questions raised by Braver man. First, we show that the information complexity of the Vector in Subspace Problem is O(n1/3), which, in turn, implies that there exists an exponential separation between quantum communication complexity and classical information complexity. Moreover, we provide an O(n) lower bound on the information complexity of the Gap Hamming Distance Problem.
We study the relative power of public randomness and quantum communication in the multiparty Simultaneous Message Passing (SMP) model. By analyzing a total Boolean function and a relational problem, we establish polynomial and exponential separations between classical public-coin protocols and quantum protocols without shared randomness or prior entanglement.
We first introduce XOR Equality, a total Boolean function in which each of k players receives an unrestricted string xj∈{0,1}n, and the referee must decide whether x1⊕⋯⊕xk=0n. For k≥8 and worst-case error at most 1/3, we prove quantum lower bounds of Ω(min{n,k2}) on total communication and Ω(min{n/k,k}) on maximum message length. A classical public-coin protocol uses two bits per player with error at most 1/4. For n=k2 and worst-case error at most 1/3, we prove that quantum protocols require maximum message length Ω(n) qubits, whereas two public-coin bits per player suffice.
We then turn to relations, for which we obtain exponential separations. Specifically, we study Multiparty Index Coordination, a k-player generalization of the two-player relation studied by Gavinsky, Kempe, Regev, and de Wolf (STOC 2006). We prove an unambiguous quantum lower bound of Ω(n1−1/k) on maximum message length, matched by a classical private-coin protocol. For any fixed error ε∈(0,1/8), we also prove a bounded-error quantum lower bound of Ω(n(k−1)/(k+1)) while we show that public-coin protocols solve the relation unambiguously with maximum message length O(logn), giving exponential separations in both regimes. The implicit constants are independent of k, and both quantum lower bounds become linear when k≥clogn for any fixed c>0.