Bounds on tradeoffs between randomness and communication complexity (Q687507)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Bounds on tradeoffs between randomness and communication complexity |
scientific article |
Statements
Bounds on tradeoffs between randomness and communication complexity (English)
0 references
18 October 1993
0 references
The authors analyze the amount of randomness used in randomized protocols for computing a binary function \(f\), the input of which being split between two parties. For various models of communication complexity, they prove tight lower bounds depending on the number of bits communicated and the deterministic communication complexity of \(f\). The proof techniques are mainly combinatorial in nature.
0 references
randomized protocols
0 references
binary function
0 references
communication complexity
0 references
lower bounds
0 references
0 references
