期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2020
卷号：2020
页码：1-10
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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.
