Fooling pairs in randomized communication complexity

DOI10.1007/978-3-319-48314-6_4MaRDI QIDQ2835016zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• A comparison of two lower-bound methods for communication complexity
• A comparison of two lower bound methods for communication complexity (extended abstract)
• scientific article; zbMATH DE number 1769898
• scientific article; zbMATH DE number 1256775
• Nondeterministic communication complexity of random Boolean functions (extended abstract)

Cites work

• A Zero-One Law for Boolean Privacy
• An information statistics approach to data stream and communication complexity
• 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
• Private vs. common random bits in communication complexity
• Probabilistic communication complexity
• The Probabilistic Communication Complexity of Set Intersection
• The randomized communication complexity of set disjointness

Cited in

(4)

• A comparison of two lower-bound methods for communication complexity
• On public-coin zero-error randomized communication complexity
• Nondeterministic communication complexity of random Boolean functions (extended abstract)
• A comparison of two lower bound methods for communication complexity (extended abstract)

This page was built for publication: Fooling pairs in randomized communication complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2835016)