Bounds on tradeoffs between randomness and communication complexity (Q687507): Difference between revisions
From MaRDI portal
ReferenceBot (talk | contribs) Changed an Item |
Set OpenAlex properties. |
||
| Property / full work available at URL | |||
| Property / full work available at URL: https://doi.org/10.1007/bf01200118 / rank | |||
Normal rank | |||
| Property / OpenAlex ID | |||
| Property / OpenAlex ID: W2132015189 / rank | |||
Normal rank | |||
Latest revision as of 08:40, 30 July 2024
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
