The communication complexity of functions with large outputs

DOI10.1007/978-3-031-32733-9_19arXiv2304.00391MaRDI QIDQ6148077

Sophie Laplante, Lila Fontes, Alexandre Nolin, Mathieu Laurière

Publication date: 11 January 2024

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

Full work available at URL: https://arxiv.org/abs/2304.00391

zbMATH Keywords

communication complexityerror reductionnon-Boolean functions

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer system organization (68Mxx) Communication complexity, information complexity (68Q11)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Towards a reverse Newman's theorem in interactive information complexity
• Certifying equality with limited interaction
• The communication complexity of addition
• An information statistics approach to data stream and communication complexity
• Choosing, agreeing, and eliminating in communication complexity
• On the distributional complexity of disjointness
• Survey on nonlocal games and operator space theory
• How to Compress Interactive Communication
• Beyond set disjointness
• Information Equals Amortized Communication
• Making Randomness Public in Unbounded-Round Information Complexity
• Interactive Information Complexity
• The complexity of agreement
• Worst-case interactive communication. II. Two messages are not optimal
• Worst-case interactive communication. I. Two messages are almost optimal
• The Probabilistic Communication Complexity of Set Intersection
• Computing with Noisy Information
• Compressing Interactive Communication Under Product Distributions
• Amortized Communication Complexity
• Communication Complexity
• An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance
• Relative Discrepancy Does Not Separate Information and Communication Complexity
• Exponential Separation of Communication and External Information
• Communication Complexity
• Interactive compression to external information
• Internal Compression of Protocols to Entropy
• Interactive compression for product distributions
• The Communication Complexity of Set Intersection and Multiple Equality Testing
• Exponential Separation of Information and Communication for Boolean Functions
• The communication complexity of enumeration, elimination, and selection

This page was built for publication: The communication complexity of functions with large outputs