Showing cs.CCShow all
2 papers · 1 filter
cs.CC2003
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…
cs.CC2002
Kolmogorov's Structure Functions and Model Selection
Nikolai Vereshchagin, Paul Vitanyi
In 1974 Kolmogorov proposed a non-probabilistic approach to statistics and model selection. Let data be finite binary strings and models be finite sets of binary strings. Consider…