Communication Complexity with Defective Randomness

Webpage for a paper by Ball, Goldreich, and Malkin


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.

Material available on-line

Additioanl grant acknowledgement: This project has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement No. 819702).

Back to either Oded Goldreich's homepage or general list of papers.