Starting with the two standard model of randomized communication complexity, we study the communication complexity of functions when the protocol has access to a defective source of randomness.
Specifically, we consider both the public-randomness and private-randomness cases, while replacing the commonly postulated perfect randomness with distributions over $\ell$ bit strings that have min-entropy at least $k\leq\ell$.
We present general upper and lower bounds on the communication complexity in these cases, where the bounds are typically linear in $\ell-k$ and also depend on the size of the fooling set for the function being computed and on its standard randomized complexity.

The wrong file was uploaded for revision 2.
This is the correct file.

Starting with the two standard model of randomized communication complexity, we study the communication complexity of functions when the protocol has access to a defective source of randomness.
Specifically, we consider both the public-randomness and private-randomness cases, while replacing the commonly postulated perfect randomness with distributions over $\ell$ bit strings that have min-entropy at least $k\leq\ell$.
We present general upper and lower bounds on the communication complexity in these cases, where the bounds are typically linear in $\ell-k$ and also depend on the size of the fooling set for the function being computed and on its standard randomized complexity.

Correcting some typos and adding a reference.

Starting with the two standard model of randomized communication complexity, we study the communication complexity of functions when the protocol has access to a defective source of randomness.
Specifically, we consider both the public-randomness and private-randomness cases, while replacing the commonly postulated perfect randomness with distributions over $\ell$ bit strings that have min-entropy at least $k\leq\ell$.
We present general upper and lower bounds on the communication complexity in these cases, where the bounds are typically linear in $\ell-k$ and also depend on the size of the fooling set for the function being computed and on its standard randomized complexity.

Correcting some typos.

Starting with the two standard model of randomized communication complexity, we study the communication complexity of functions when the protocol has access to a defective source of randomness.
Specifically, we consider both the public-randomness and private-randomness cases, while replacing the commonly postulated perfect randomness with distributions over $\ell$ bit strings that have min-entropy at least $k\leq\ell$.
We present general upper and lower bounds on the communication complexity in these cases, where the bounds are typically linear in $\ell-k$ and also depend on the size of the fooling set for the function being computed and on its standard randomized complexity.