Individual Communication Complexity

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

We initiate the theory of communication complexity of individual inputs held by the agents, rather than worst-case or average-case. We consider total, partial, and partially correct protocols, one-way versus two-way, with and without help bits. The results are expressed in trems of Kolmogorov complexity.
11 pages, LaTeX

Keywords

Computational Complexity, Distributed, Parallel, and Cluster Computing, F.1; F.2

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/31518

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/cs/0304012
 http://arxiv.org/abs/cs/0304012

Collections

arXiv