CISPA
Browse
FLLN19_CC_large_output.pdf (470.29 kB)

The communication complexity of functions with large outputs.

Download (470.29 kB)
preprint
posted on 2024-02-27, 07:51 authored by Lila Fontes, Sophie Laplante, Mathieu Laurière, Alexandre Nolin
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 2k 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.

History

Primary Research Area

  • Algorithmic Foundations and Cryptography

BibTeX

@misc{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 = 4 }

Usage metrics

    Categories

    No categories selected

    Licence

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC