Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #3 to TR20-054 | 21st June 2021 18:14

#### Communication Complexity with Defective Randomness

Revision #3
Authors: Marshall Ball, Oded Goldreich, Tal Malkin
Accepted on: 21st June 2021 18:14
Keywords:

Abstract:

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.

Changes to previous version:

The wrong file was uploaded for revision 2.
This is the correct file.

Revision #2 to TR20-054 | 5th November 2020 16:12

#### Communication Complexity with Defective Randomness

Revision #2
Authors: Marshall Ball, Oded Goldreich, Tal Malkin
Accepted on: 5th November 2020 16:12
Keywords:

Abstract:

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.

Changes to previous version:

Correcting some typos and adding a reference.

Revision #1 to TR20-054 | 4th November 2020 09:27

#### Communication Complexity with Defective Randomness

Revision #1
Authors: Marshall Ball, Oded Goldreich, Tal Malkin
Accepted on: 4th November 2020 09:27
Keywords:

Abstract:

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.

Changes to previous version:

Correcting some typos.

### Paper:

TR20-054 | 22nd April 2020 22:02

#### Communication Complexity with Defective Randomness

TR20-054
Authors: Marshall Ball, Oded Goldreich, Tal Malkin
Publication: 22nd April 2020 22:02
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.