Fleischer, Rudolf; Jung, Hermann; Mehlhorn, Kurt A communication-randomness tradeoff for two-processor systems. (English) Zbl 0828.68088 Inf. Comput. 116, No. 2, 155-161 (1995). 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. Cited in 1 Document MSC: 68Q25 Analysis of algorithms and problem complexity 94A05 Communication theory 68Q30 Algorithmic information theory (Kolmogorov complexity, etc.) Keywords:communication complexity; Las Vegas protocol PDFBibTeX XMLCite \textit{R. Fleischer} et al., Inf. Comput. 116, No. 2, 155--161 (1995; Zbl 0828.68088) Full Text: DOI