Communication complexity with defective randomness

Marshall Ball, Oded Goldreich, Tal Malkin

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.

Original languageEnglish (US)
Title of host publication36th Computational Complexity Conference, CCC 2021
EditorsValentine Kabanets
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959771931
StatePublished - Jul 1 2021
Event36th Computational Complexity Conference, CCC 2021 - Virtual, Toronto, Canada
Duration: Jul 20 2021Jul 23 2021

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
ISSN (Print)1868-8969


Conference36th Computational Complexity Conference, CCC 2021
CityVirtual, Toronto


  • Min-Entropy
  • Randomized communication complexity
  • Randomness extraction

ASJC Scopus subject areas

  • Software


Dive into the research topics of 'Communication complexity with defective randomness'. Together they form a unique fingerprint.

Cite this