^{1} Department of Computer Science, Science and Technology, Aarhus University^{2} Dartmouth College^{3} University of Massachusetts Amberst^{4} Department of Computer Science, Science and Technology, Aarhus University

Abstract:

The \textsc{equality} problem is usually one's first encounter with communication complexity and is one of the most fundamental problems in the field. Although its deterministic and randomized communication complexity were settled decades ago, we find several new things to say about the problem by focusing on two subtle aspects. The first is to consider the {\em expected} communication cost (at a worst-case input) for a protocol that uses limited interaction---i.e., a bounded number of rounds of communication---and whose error probability is zero or close to it. The second is to consider the {\em information cost} of such protocols. We obtain asymptotically optimal rounds-versus-communication and rounds-versus-information tradeoffs for the problem. For the case of zero-error communication cost, we obtain essentially matching bounds, up to a tiny additive constant. As an application of our information cost bounds, we obtain new bounded-round randomized lower bounds for the \textsc{or-equality} problem that have a direct-sum flavor. Such lower bounds were previously known only for deterministic protocols or one-round randomized protocols. The \textsc{or-equality} problem is in turn closely related to the \textsc{disjointness} problem for small sets (sometimes called k-\textsc{disj}), and we obtain tight lower bounds for that problem as well.

Type:

Journal article

Language:

English

Published in:

Electronic Colloquium on Computational Complexity, 2012, Issue TR12-153

Keywords:

bounded-round; Communication complexity; direct sum; disjointness; equality