Bounds on tradeoffs between randomness and communication complexity (Q687507)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Bounds on tradeoffs between randomness and communication complexity |
scientific article; zbMATH DE number 431312
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Bounds on tradeoffs between randomness and communication complexity |
scientific article; zbMATH DE number 431312 |
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
