Paul Vitanyi has a total of 34 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Fast Whole-Genome Phylogeny by Compression: the COVID-19 case

    by Rudi L. Cilibrasi, Paul M.B. Vitanyi

    We analyze the whole-genome phylogeny and taxonomy of the SARS-CoV-2 virus, causing the COVID-19 disease, using compres- sion in the form of the alignment-free NCD (Normalized Compression Distance) method to assess similarity. We compare the SARS-CoV-2 virus with a database of over 6,500 viruses. The results comprise that the SARS- CoV-2 virus is closest in that database to the RaTG13 virus and rather close to the bat SARS-like corona viruses bat-SL-CoVZXC21 and bat-SL- CoVZC45. Over 6,500 viruses are identified (given by their registration code) with larger NCD’s. The NCD’s are compared with the NCD’s between the mtDNA’s of familiar species. We treat the question whether Pangolins are involved in the SARS-CoV-2 virus. The NCD method or shortly the compression method is simpler and possibly faster than any other whole-genome method, which makes it the ideal tool to explore phylogeny. Here we use it for the complex case of determining this similarity between the COVID-19 virus SARS-CoV-2 and many other viruses. The resulting phylogeny and taxonomy closely matches earlier efforts by alignment-based methods and a machine-learning method, providing the most compelling evidence to date for the compression method showing that one can achieve equivalent results both simply and fast.

  • Open Access

    Fast Whole-Genome Phylogeny of the COVID-19 Virus SARS-CoV-2 by Compression

    by Rudi L. Cilibrasi, Paul M.B. Vitányi

    We analyze the whole genome phylogeny and taxonomy of the SARS-CoV-2 virus using compression. This is a new fast alignment-free method called the “normalized compression distance” (NCD) method. It discovers all effective similarities based on Kolmogorov complexity. The latter being incomputable we approximate it by a good compressor such as the modern zpaq. The results comprise that the SARS-CoV-2 virus is closest to the RaTG13 virus and similar to two bat SARS-like coronaviruses bat-SL-CoVZXC21 and bat-SL-CoVZC4. The similarity is quantified and compared with the same quantified similarities among the mtDNA of certain species. We treat the question whether Pangolins are involved in the SARS-CoV-2 virus. The compression method is simpler and possibly faster than any other whole genome method, which makes it the ideal tool to explore phylogeny.


  • Open Access

    How Incomputable Is Kolmogorov Complexity?

    by Paul M.B. Vitányi

    Kolmogorov complexity is the length of the ultimately compressed version of a file (i.e., anything which can be put in a computer). Formally, it is the length of a shortest program from which the file can be reconstructed. We discuss the incomputability of Kolmogorov complexity, which formal loopholes this leaves us with, recent approaches to compute or approximate Kolmogorov complexity, which approaches are problematic, and which approaches are viable.


  • On the average‐case complexity of Shellsort

    by Paul Vitányi

  • Open Access

    Identification of Probabilities

    by 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 input: that is, to infer a probabilistic model from a sample. The practical problems of such inference are substantial: the brain has limited data and restricted computational resources. But there is a more fundamental question: is the problem of inferring a probabilistic model from a sample possible even in principle? We explore this question and find some surprisingly positive and general results. First, for a broad class of probability distributions characterised by computability restrictions, we specify a learning algorithm that will almost surely identify a probability distribution in the limit given a finite i.i.d. sample of sufficient but unknown length. This is similarly shown to hold for sequences generated by a broad class of Markov chains, subject to computability assumptions. The technical tool is the strong law of large numbers. Second, for a large class of dependent sequences, we specify an algorithm which identifies in the limit a computable measure for which the sequence is typical, in the sense of Martin-Lof (there may be more than one such measure). The technical tool is the theory of Kolmogorov complexity. We analyse the associated predictions in both cases. We also briefly consider special cases, including language learning, and wider theoretical implications for psychology.

  • Open Access

    On The Average-Case Complexity of Shellsort

    by 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 could be checked. A special case of this lower bound yields the general Jiang-Li-Vit\'anyi lower bound. We obtain new results e.g. determining the average-case complexity precisely in the Yao-Janson-Knuth 3-pass case.

  • Open Access

    Identification of probabilities

    by Paul M.B. Vitányi, Nick Chater


  • Open Access

    A Lower Bound on the Average-Case Complexity of Shellsort

    by Tao Jiang, Ming Li, Paul Vitanyi

    We prove a general lower bound on the average-case complexity of Shellsort: the average number of data-movements (and comparisons) made by a $p$-pass Shellsort for any incremental sequence is $\Omega (pn^{1 + 1/p})$ for every $p$. The proof method is an incompressibility argument based on Kolmogorov complexity. Using similar techniques, the average-case complexity of several other sorting algorithms is analyzed.

  • Open Access

    Algorithmic Identification of Probabilities

    by Paul M. B. Vitanyi, Nick Chater

    TThe problem is to identify a probability associated with a set of natural numbers, given an infinite data sequence of elements from the set. If the given sequence is drawn i.i.d. and the probability mass function involved (the target) belongs to a computably enumerable (c.e.) or co-computably enumerable (co-c.e.) set of computable probability mass functions, then there is an algorithm to almost surely identify the target in the limit. The technical tool is the strong law of large numbers. If the set is finite and the elements of the sequence are dependent while the sequence is typical in the sense of Martin-L\"of for at least one measure belonging to a c.e. or co-c.e. set of computable measures, then there is an algorithm to identify in the limit a computable measure for which the sequence is typical (there may be more than one such measure). The technical tool is the theory of Kolmogorov complexity. We give the algorithms and consider the associated predictions.