TY - GEN
T1 - Communication complexity with defective randomness
AU - Ball, Marshall
AU - Goldreich, Oded
AU - Malkin, Tal
N1 - Funding Information:
Funding This work was supported in part by the Office of the Director of National Intelligence (ODNI), Intelligence Advanced Research Projects Activity (IARPA) via Contract No. 2019-1902070006. The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies, either express or implied, of ODNI, IARPA, or the U.S. Government. The U.S. Government is authorized to reproduce and distribute reprints for governmental purposes notwithstanding any copyright annotation therein. Marshall Ball: Partially supported by an IBM Research PhD Fellowship. Oded Goldreich: Partially supported by an ISF grant number (Nr. 1146/18); research was conducted while he enjoyed the hospitality of the computer science department at Columbia University.
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 -