Revision #1 Authors: Joshua Brody, Amit Chakrabarti, Ranganath Kondapally

Accepted on: 11th April 2013 21:16

Downloads: 857

Keywords:

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-cost tradeoffs

for \textsc{equality}: both expected communication cost and information

cost scale as $\Theta(\log\log\cdots\log n)$, with $r-1$ logs, where $r$

is the number of rounds. 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.

Updated in light of recently-announced related work

TR12-153 Authors: Joshua Brody, Amit Chakrabarti, Ranganath Kondapally

Publication: 9th November 2012 20:49

Downloads: 1962

Keywords:

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.