Individual Communication Complexity
classification
💻 cs.CC
cs.DC
keywords
complexitycommunicationindividualagentsaverage-casebitsconsidercorrect
read the original abstract
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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.