Paul Vitanyi#

Short laudatio by Krzysztof R. Apt#

Paul Vitanyi has made several fundamental contributions to various fields in computer science, notably complexity theory, distributed computing, learning, information theory and Kolmogorov complexity:

1. Showed lower bound on simulation of 2 worktapes by 1 in TMs (n -> n^2 which is optimal). Open for 30 years
2. Showed how to real-time simulate multicounter machine by 1-tape TM. Open for 30 years
3. Showed that in real-time two heads are better than two tapes for a TM (on its worktape). Open for 40 years
4. Showed how to implement a multi-user wait-free atomic variable (registers). Ditto with unbounded information (known as Vitanyi-Awerbuch algorithm)
5. First results on quorums in distributed computing
6. Proved a first general lower bound on the average running time of p-pass Shellsort. Open for 40 years
7. Pioneered new methods and problems in Kolmogorov complexity, "the Incompressibility Method"
8. Invented the theory/application for a universal similarity measure between finite objects based on compression that is alignment-free, feature-free, parameter-free and used now ubiquitously in genomics, data-mining
9. Invented a universal relative semantics using internet
10. P. Vitanyi's and M. Li book An Introduction to Kolmogorov Complexity and its Applications, Springer-Verlag, New York, 1993 (3rd Edition 2008, 790 pp.) is the standard book in the field. Part of this book have been translated into Chinese, Russian and Japanese

---

Any further pages in alphabetic order of their title as created by you.
#

Just click at "Create new page", then type a short title and click OK, then add information on the empty page presented to you (including maybe a picture from your harddisk or a pdf-file by using the "Upload" Button) and finally click at "Save".
...no Data available yet!