62 citations · 130 across the 17 of their papers we have counts for
5 papers · 1 filter
Nonapproximablity of the Normalized Information Distance
Sebastiaan A. Terwijn, Leen Torenvliet, Paul M. B. Vitanyi
Normalized information distance (NID) uses the theoretical notion of Kolmogorov complexity, which for practical purposes is approximated by the length of the compressed version of…
Distributed elections in an Archimedean ring of processors
Paul M. B. Vitanyi
Unlimited asynchronism is intolerable in real physically distributed computer systems. Such systems, synchronous or not, use clocks and timeouts. Therefore the magnitudes of elapse…
Analysis of Sorting Algorithms by Kolmogorov Complexity (A Survey)
Paul M. B. Vitanyi
Recently, many results on the computational complexity of sorting algorithms were obtained using Kolmogorov complexity (the incompressibility method). Especially, the usually hard…
Normalized Web Distance and Word Similarity
Rudi L. Cilibrasi, Paul M. B. Vitanyi
There is a great deal of work in cognitive psychology, linguistics, and computer science, about using word (or phrase) frequencies in context in text corpora to develop measures fo…
Information Distance in Multiples
Paul M. B. Vitanyi
Information distance is a parameter-free similarity measure based on compression, used in pattern recognition, data mining, phylogeny, clustering, and classification. The notion of…