×

A communication-randomness tradeoff for two-processor systems. (English) Zbl 0828.68088

Summary: We present a tight tradeoff between the expected communication complexity \(\overline 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/\overline C)\) lower bound on the number of random bits used by any Las Vegas protocol, \(\Omega(n)\leq \overline C\leq O(n^2)\). We also show that expected communication complexity \(\overline C\), \(\Omega(n\log n)\leq \overline C\leq O(n^2)\), can be achieved using no more than \(\log(n^2/\overline C)+ \lceil\log(2+ \log(n^2/\overline C))\rceil+ 6\) random bits.

MSC:

68Q25 Analysis of algorithms and problem complexity
94A05 Communication theory
68Q30 Algorithmic information theory (Kolmogorov complexity, etc.)
PDFBibTeX XMLCite
Full Text: DOI