Individual Communication Complexity

Harry Buhrman, Hartmut Klauck, Nikolai Vereshchagin +1

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 correc…