Bounds on tradeoffs between randomness and communication complexity
type: Item
instance of: scholarly article
title: Bounds on tradeoffs between randomness and communication complexity
zbMATH Open document ID: 0783.68053
DOI: 10.1007/BF01200118
author: Ran Canetti
author: Oded Goldreich
published in: Computational Complexity
publication date: 1993-10-18T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68W15
zbMATH DE Number: 431312
zbMATH Keywords: randomized protocols
zbMATH Keywords: binary function
zbMATH Keywords: communication complexity
zbMATH Keywords: lower bounds
reviewed by: Patrick Jaillet
MaRDI profile type: Publication
cites work: Factoring polynomials using fewer random bits
cites work: Randomness in interactive proofs
cites work: Routing, merging, and sorting on parallel models of computation
cites work: How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
cites work: Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
cites work: Amortized Communication Complexity
cites work: Impossibility of distributed consensus with one faulty process
cites work: Probability Inequalities for Sums of Bounded Random Variables
cites work: Private vs. common random bits in communication complexity
cites work: Probabilistic communication complexity
cites work: A Time-Randomness Trade-Off for Oblivious Routing
cites work: A Scheme for Fast Parallel Communication
full work available at URL: https://doi.org/10.1007/bf01200118
OpenAlex ID: W2132015189
description: scientific article; zbMATH DE number 431312