Individual communication complexity
Copyright policy )Individual communication complexity
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
- Lomonosov Moscow State University Russian Federation
- Moscow Witte University Russian Federation
- Centrum Wiskunde & Informatica Netherlands
- Institute for Advanced Study United States
- Dutch Research Council Netherlands
FOS: Computer and information sciences, Computer Networks and Communications, F.1, Applied Mathematics, F.2, Communication complexity, Kolmogorov complexity, Computational Complexity (cs.CC), F.1; F.2, individual complexity, Individual complexity, Algorithmic information theory (Kolmogorov complexity, etc.), Theoretical Computer Science, Computer Science - Computational Complexity, Computational Theory and Mathematics, Computer Science - Distributed, Parallel, and Cluster Computing, communication complexity, Distributed, Parallel, and Cluster Computing (cs.DC)
FOS: Computer and information sciences, Computer Networks and Communications, F.1, Applied Mathematics, F.2, Communication complexity, Kolmogorov complexity, Computational Complexity (cs.CC), F.1; F.2, individual complexity, Individual complexity, Algorithmic information theory (Kolmogorov complexity, etc.), Theoretical Computer Science, Computer Science - Computational Complexity, Computational Theory and Mathematics, Computer Science - Distributed, Parallel, and Cluster Computing, communication complexity, Distributed, Parallel, and Cluster Computing (cs.DC)
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).4 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!