Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR12-153 | 11th April 2013 21:16

Certifying Equality With Limited Interaction

RSS-Feed

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-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.



Changes to previous version:

Updated in light of recently-announced related work


Paper:

TR12-153 | 9th November 2012 20:45

Certifying Equality With Limited Interaction





TR12-153
Authors: Joshua Brody, Amit Chakrabarti, Ranganath Kondapally
Publication: 9th November 2012 20:49
Downloads: 3375
Keywords: 


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.



ISSN 1433-8092 | Imprint