Ball, Marshall
[Verfasser:in];
Goldreich, Oded
[Verfasser:in];
Malkin, Tal
[Verfasser:in]
;
Marshall Ball and Oded Goldreich and Tal Malkin
[Mitwirkende:r]
Communication Complexity with Defective Randomness
Anmerkungen:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Beschreibung:
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 𝓁 bit strings that have min-entropy at least k ≤ 𝓁. We present general upper and lower bounds on the communication complexity in these cases, where the bounds are typically linear in 𝓁-k and also depend on the size of the fooling set for the function being computed and on its standard randomized complexity.