62 citations · 63 across the 4 of their papers we have counts for
26 papers
Time, Space, and Energy in Reversible Computing
Paul Vitanyi
We survey results of a quarter century of work on computation by reversible general-purpose computers (in this setting Turing machines), and general reversible simulation of irreve…
Universal Similarity
Paul Vitanyi
We survey a new area of parameter-free similarity distance measures useful in data-mining, pattern recognition, learning and automatic semantics extraction. Given a family of dista…
Clustering by compression
Rudi Cilibrasi, Paul Vitanyi
We present a new method for clustering based on compression. The method doesn't use subject-specific features or background knowledge, and works as follows: First, we determine a u…
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…
Algorithmic Chaos
Paul Vitanyi
Many physical theories like chaos theory are fundamentally concerned with the conceptual tension between determinism and randomness. Kolmogorov complexity can express randomness in…
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…