Fooling Pairs in Randomized Communication Complexity

DOI10.1007/978-3-319-48314-6_4zbMath1482.68103OpenAlexW1697076466MaRDI QIDQ2835016

Shay Moran, Makrand Sinha, Amir Yehudayoff

Publication date: 1 December 2016

Published in: Structural Information and Communication Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-48314-6_4

Mathematics Subject Classification ID

Randomized algorithms (68W20) Communication complexity, information complexity (68Q11)

Cites Work

• Unnamed Item
• Probabilistic communication complexity
• An information statistics approach to data stream and communication complexity
• Private vs. common random bits in communication complexity
• Geometric arguments yield better bounds for threshold circuits and distributed computing
• How to Compress Interactive Communication
• Lower Bounds in Communication Complexity
• Perturbed Identity Matrices Have High Rank: Proof and Applications
• The Probabilistic Communication Complexity of Set Intersection
• Communication Complexity
• A Zero-One Law for Boolean Privacy