Item

Abstract

We present a tight tradeoff between the expected communication complexity
$\bar{C}$ (for a two-processor system) and the number $R$ of random bits used
by any Las Vegas protocol for the list-nondisjointness function of two lists
of $n$ numbers of $n$ bits each. This function evaluates to $1$ if and only if
the two lists correspond in at least one position. We show a
$\log(n^2/\bar{C})$ lower bound on the number of random bits used by any Las
Vegas protocol, $\Omega(n)\le\bar{C}\le O(n^2)$. We also show that expected
communication complexity $\bar{C}$, $\Omega(n\log n) \le\bar{C}\le O(n^2)$,
can be achieved using no more than $\log(n^2/\bar{C}) +
\lceil\log(2+\log(n^2/\bar{C}))\rceil+6$ random bits.",
xxx-references = "STOC::AhoUY83,
FOCS::CanettiG90,
STOC::Furer87,
STOC::HalstenbergR88,
STOC::KrizancPU88,
FOCS::LovaszS88,
STOC::MehlhornS82,
STOC::PapadimitriouS82,
FOCS::Yao77,
STOC::Yao79,
FOCS::Yao83",
references = "\cite{STOC::AhoUY1983}
\cite{FOCS::CanettiG1990}
\cite{STOC::Furer1987}
\cite{STOC::HalstenbergR1988}
\cite{STOC::KrizancPU1988}
\cite{FOCS::LovaszS1988}
\cite{STOC::MehlhornS1982}
\cite{STOC::PapadimitriouS1982}
\cite{FOCS::Yao1977}
\cite{STOC::Yao1979}
\cite{FOCS::Yao1983}