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

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.