Bounds on tradeoffs between randomness and communication complexity

DOI10.1007/BF01200118zbMath0783.68053OpenAlexW2132015189MaRDI QIDQ687507

Ran Canetti, Oded Goldreich

Publication date: 18 October 1993

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01200118

zbMATH Keywords

lower boundscommunication complexitybinary functionrandomized protocols

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Distributed algorithms (68W15)

Related Items (4)

On multi-partition communication complexity ⋮ On the number of random bits in totally private computation ⋮ Bounds on tradeoffs between randomness and communication complexity ⋮ Computing (and Life) Is All about Tradeoffs

Cites Work

• Probabilistic communication complexity
• Bounds on tradeoffs between randomness and communication complexity
• Factoring polynomials using fewer random bits
• Routing, merging, and sorting on parallel models of computation
• Private vs. common random bits in communication complexity
• Randomness in interactive proofs
• How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
• A Time-Randomness Trade-Off for Oblivious Routing
• Impossibility of distributed consensus with one faulty process
• Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
• A Scheme for Fast Parallel Communication
• Amortized Communication Complexity
• Probability Inequalities for Sums of Bounded Random Variables

This page was built for publication: Bounds on tradeoffs between randomness and communication complexity