The communication complexity of functions with large outputs

DOI10.1007/978-3-031-32733-9_19MaRDI QIDQ6148077zbMATH OpenFDO

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

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

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

Abstract: We study the two-party communication complexity of functions with large outputs, and show that the communication complexity can greatly vary depending on what output model is considered. We study a variety of output models, ranging from the open model, in which an external observer can compute the outcome, to the XOR model, in which the outcome of the protocol should be the bitwise XOR of the players' local outputs. This model is inspired by XOR games, which are widely studied two-player quantum games. We focus on the question of error-reduction in these new output models. For functions of output size k, applying standard error reduction techniques in the XOR model would introduce an additional cost linear in k. We show that no dependency on k is necessary. Similarly, standard randomness removal techniques, incur a multiplicative cost of $2^k$ in the XOR model. We show how to reduce this factor to O(k). In addition, we prove analogous error reduction and randomness removal results in the other models, separate all models from each other, and show that some natural problems, including Set Intersection and Find the First Difference, separate the models when the Hamming weights of their inputs is bounded. Finally, we show how to use the rank lower bound technique for our weak output models.

Cites work

• Amortized Communication Complexity
• An information statistics approach to data stream and communication complexity
• Beyond set disjointness: the communication complexity of finding the intersection
• Certifying equality with limited interaction
• Choosing, agreeing, and eliminating in communication complexity
• Communication Complexity
• Communication Complexity
• Compressing interactive communication under product distributions
• Computing with Noisy Information
• Exponential separation of communication and external information
• Exponential separation of information and communication for Boolean functions
• How to compress interactive communication
• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• scientific article; zbMATH DE number 524134 (Why is no real title available?)
• scientific article; zbMATH DE number 1775389 (Why is no real title available?)
• scientific article; zbMATH DE number 7250149 (Why is no real title available?)
• scientific article; zbMATH DE number 6292622 (Why is no real title available?)
• Information Equals Amortized Communication
• Interactive compression for product distributions
• Interactive compression to external information
• Interactive Information Complexity
• Internal Compression of Protocols to Entropy
• Making randomness public in unbounded-round information complexity
• On the distributional complexity of disjointness
• Random graphs.
• Relative discrepancy does not separate information and communication complexity
• Simplified separation of information and communication
• Survey on nonlocal games and operator space theory
• The communication complexity of addition
• The communication complexity of enumeration, elimination, and selection
• The communication complexity of gap Hamming distance
• The communication complexity of set intersection and multiple equality testing
• The complexity of agreement
• The Probabilistic Communication Complexity of Set Intersection
• Towards a reverse Newman's theorem in interactive information complexity
• Worst-case interactive communication. I. Two messages are almost optimal
• Worst-case interactive communication. II. Two messages are not optimal

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

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