Individual Communication Complexity
Buhrman, Harry · Klauck, Hartmut · Vereshchagin, Nikolai · Vitanyi, Paul
Original · EN
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.
English translation
This paper has no Arabic translation yet. Be the first: it takes a few seconds, and the result is stored for every future reader.