Note: |
|
(LaTeX) 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} |
URL for the Abstract: |
|
Categories,
Keywords: |
|
HyperLinks / References / URLs: |
|
Copyright Message: |
|
Personal Comments: |
|
Download
Access Level: |
Public |
|