The communication complexity of the universal relation
Gábor Tardos, Uri Zwick · 2002
Consider the following communication problem. Alice gets a word x/spl isin/{0,1}/sup n/ and Bob gets a word y/spl isin/{0,1}/sup n/. Alice and Bob are told that x/spl ne/y. Their goal is to find an index 1/spl les/i/spl les/n such that x/sub i//spl ne/y/sub i/ (the index i should be known to both of them). This problem is one of the most basic communication problems. It arises naturally from the correspondence between circuit depth and communication complexity discovered by M. Karchmer and A. Wigderson (1990). We present three protocols using which Alice and Bob can solve the problem by exchanging at most it n+2 bits. One of this protocols is due to S. Rudich and G. Tardos. These protocols improve the previous upper bound of n+log* n, obtained by M. Karchmer. We also show that any protocol for solving the problem must exchange, in the worst case, at least n+1 bits. This improves a simple lower bound of n-1 obtained by Karchmer. Our protocols, therefore, are at most one bit away from optimality.