A COMMUNICATION-RANDOMNESS TRADEOFF FOR 2-PROCESSOR SYSTEMS

We present a tig ht tradeoff between the expected communication comple xity ($) over bar C (for a two-processor system) and the number R of r andom bits used by any Las Vegas protocol for the list-nondisjointness function of two lists of n numbers of n bits each. This function eval uates to 1 if and only if the two lists correspond in at least one pos ition. We show a log(n(2)/($) over bar C) lower bound on the number of random bits used by any Las Vegas protocol, Omega(n) less than or equ al to ($) over bar C less than or equal to O(n(2)). We also show that expected communication complexity ($) over bar C, Omega(n log n) less than or equal to ($) over bar C less than or equal to O(n(2)), can be achieved using no more than [log(n(2)/($) over bar C) + log(2 + log(n( 2)/($) over bar C))] + 6 random bits. (C) 1995 Academic Press, Inc.