CISPA
Browse
FLLN19_CC_large_output (1).pdf (470.29 kB)

The Communication Complexity of Functions with Large Outputs

Download (470.29 kB)
conference contribution
posted on 2024-03-26, 08:51 authored by Lila Fontes, Sophie Laplante, Mathieu Laurière, Alexandre NolinAlexandre Nolin
Home Structural Information and Communication Complexity Conference paper The Communication Complexity of Functions with Large Outputs Lila Fontes, Sophie Laplante, Mathieu Laurière & Alexandre Nolin Conference paper First Online: 25 May 2023 272 Accesses Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 13892)) 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 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.

History

Primary Research Area

  • Algorithmic Foundations and Cryptography

Name of Conference

Structural Information and Communication Complexity (SIROCCO)

Journal

Electron. Colloquium Comput. Complex.

Volume

13892

Page Range

427-458

Publisher

Springer Nature

Open Access Type

  • Green

BibTeX

@inproceedings{Fontes:Laplante:Laurière:Nolin:2023, title = "The Communication Complexity of Functions with Large Outputs", author = "Fontes, Lila" AND "Laplante, Sophie" AND "Laurière, Mathieu" AND "Nolin, Alexandre", year = 2023, month = 5, journal = "Electron. Colloquium Comput. Complex.", pages = "427--458", publisher = "Springer Nature", issn = "1611-3349", doi = "10.1007/978-3-031-32733-9_19" }