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}