136 citations · 749 across the 72 of their papers we have counts for
74 papers
The cluster structure function
Andrew R. Cohen, Paul M. B. Vitányi
For each partition of a data set into a given number of parts there is a partition such that every part is as much as possible a good model (an "algorithmic sufficient statistic")…
How incomputable is Kolmogorov complexity?
Paul Vitanyi
Kolmogorov complexity is the length of the ultimately compressed version of a file (that is, anything which can be put in a computer). Formally, it is the length of a shortest prog…
Logical depth for reversible Turing machines with an application to the rate of decrease in logical depth for general Turing machines
Paul MB Vitanyi
The logical depth of a {\em reversible} Turing machine equals the shortest running time of a shortest program for it. This is applied to show that the result in L.F. Antunes, A. So…
Identification of Probabilities
Paul M. B. Vitanyi, Nick Chater
Within psychology, neuroscience and artificial intelligence, there has been increasing interest in the proposal that the brain builds probabilistic models of sensory and linguistic…
Web Similarity in Sets of Search Terms using Database Queries
Andrew R. Cohen, Paul M. B. Vitanyi
Normalized web distance (NWD) is a similarity or normalized semantic distance based on the World Wide Web or another large electronic database, for instance Wikipedia, and a search…
On The Average-Case Complexity of Shellsort
Paul M. B. Vitanyi
We prove a lower bound expressed in the increment sequence on the average-case complexity of the number of inversions of Shellsort. This lower bound is sharp in every case where it…