Individual Communication Complexity

Simple item page
dc.creatorBuhrman, Harry
dc.creatorKlauck, Hartmut
dc.creatorVereshchagin, Nikolai
dc.creatorVitanyi, Paul
dc.date2003-04-08
dc.date.accessioned2026-07-07T03:19:35Z
dc.date.available2026-07-07T03:19:35Z
dc.descriptionWe 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.
dc.description11 pages, LaTeX
dc.identifierhttps://arxiv.org/abs/cs/0304012
dc.identifierhttp://arxiv.org/abs/cs/0304012
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/31518
dc.subjectComputational Complexity
dc.subjectDistributed, Parallel, and Cluster Computing
dc.subjectF.1; F.2
dc.titleIndividual Communication Complexity
dc.typetext

Files

Collections

arXiv