A Communication-Randomness Tradeoff for Two-Processor Systems

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

Authors

• R. Fleischer
• H. Jung
• K. Mehlhorn

Keywords

No keywords are indexed for this paper.