Skip to content
DraconiticResearch
Search Sources API
206,690 studies31 sourcesUpdated 18 min ago
PreprintCC BY 4.0HAL

A note on the nondeterministic communication complexity of equality

  • Mathieu Hoyrup
Open at sourcePDFCite

Abstract

This note gathers results estimating the nondeterministic communication complexity of equality. These results are only partially proved in the reference textbooks on communication complexity, and the purpose of this note is to state the results and their proofs in a hopefully clear and explicit manner. Moreover, the nondeterministic communication complexity of inequality is usually given approximately but its exact value turns out to be known.

Related

  1. A note on the complexity of random subspace model-based methods for derivative-free optimization
    Coralia Cartis, Lindon Roberts
    arXivPreprintarXiv licenceFull textOptimisation & controlarXiv
  2. Recognizable Picture Languages: Separating UREC from coUREC via Communication Complexity
    Antonin Callard, Andrei Romashchenko, Véronique Terrier +1
    HALPreprintCC BY 4.0Full textGeneral mathematicsHAL
  3. Infinite Communication Complexity and KW Games
    Evan Leach
    arXivPreprintarXiv licenceFull textLogic & foundationsarXiv
  4. A Note on Binary Quadratic Systems and their relation to complexity theory
    Gabriele Radici, Massimiliano Sala
    arXivPreprintCC BY 4.0Full textAlgebra & number theoryarXiv
  5. Minimizing the Arithmetic and Communication Complexity of Jacobi's Method for Eigenvalues and Singular Values: Part Two -- Parallel Algorithms
    James Demmel, Hengrui Luo, Ryan Schneider +1
    arXivPreprintCC BY-NC-ND 4.0Full textNumerical analysis & scientific computingarXiv

Cite

BibTeXRIS
BibTeX
@misc{hoyrup2026note,
  title = {{A note on the nondeterministic communication complexity of equality}},
  author = {Mathieu Hoyrup},
  howpublished = {HAL},
  year = {2026},
  month = sep,
  url = {https://inria.hal.science/hal-05742346v1},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - A note on the nondeterministic communication complexity of equality
AU  - Mathieu Hoyrup
PY  - 2026
DA  - 2026/09/08
PB  - HAL
UR  - https://inria.hal.science/hal-05742346v1
AB  - This note gathers results estimating the nondeterministic communication complexity of equality. These results are only partially proved in the reference textbooks on communication complexity, and the purpose of this note is to state the results and their proofs in a hopefully clear and explicit manner. Moreover, the nondeterministic communication complexity of inequality is usually given approximately but its exact value turns out to be known.
ER  -