2003/04/08 by Harry Buhrman, Buhrman, Harry, Hartmut Klauck +5
Computer Science · #Computational Complexity (cs.CC) #Distributed #F.1 #F.2 #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC) #cs.CC #cs.DC
paper · pdf · doi:10.48550/arxiv.cs/0304012
11 pages, LaTeX
arxiv created 2003/04/08 · arxiv updated 2009/11/30
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.