Individual communication complexity

摘要

We initiate the theory of communication complexity of individual inputs held by the agents. This contrasts with the usual communication complexity model, where one counts the amount of communication for the worst-case or the average-case inputs. The individual communication complexity gives more information (the worst-case and the average-case can be derived from it but not vice versa) and may in some cases be of more interest. It is given in terms of the Kolmogorov complexities of the individual inputs. There are different measures of communication complexity depending on whether the protocol is guaranteed to be correct for all inputs or not, and whether there's one-way or two-way communication. Bounds are provided for the communication of specific functions and connections between the different communication measures are shown. Some counter-intuitive results: for deterministic protocols that need to communicate Bob's input to Alice they need to communicate all of Bob's input (rather than the information difference with Alice's input), and there are so-called “non-communicable” inputs.