TY - GEN
T1 - Communication complexity with defective randomness
AU - Ball, Marshall
AU - Goldreich, Oded
AU - Malkin, Tal
N1 - Publisher Copyright:
© Marshall Ball, Oded Goldreich, and Tal Malkin; licensed under Creative Commons License CC-BY 4.0
PY - 2021/7/1
Y1 - 2021/7/1
N2 - 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.
AB - 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.
KW - Min-Entropy
KW - Randomized communication complexity
KW - Randomness extraction
UR - http://www.scopus.com/inward/record.url?scp=85115293954&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85115293954&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.CCC.2021.14
DO - 10.4230/LIPIcs.CCC.2021.14
M3 - Conference contribution
AN - SCOPUS:85115293954
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 36th Computational Complexity Conference, CCC 2021
A2 - Kabanets, Valentine
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 36th Computational Complexity Conference, CCC 2021
Y2 - 20 July 2021 through 23 July 2021
ER -