Publications

Books

M. Li and P.M.B. Vitanyi, Description Complexity and Applications, China Science Press, Beijing, China, December 1998 (Chinese translation from the original English by Cheng Qi).
M. Li and P.M.B. Vitanyi, An Introduction to Kolmogorov Complexity and its Applications, Springer-Verlag, New York, First Edition, 1993, Second Edition, 1997 (xx+637pp). Third Edition, 2008 (xxiii+790pp) Fourth Edition, 2019 (xxiii+834pp)
Journal Articles
Conference Articles
- P.M.B. Vitanyi, Information Distance: New Developments, (Extended Abstract) pp. 71-74 in: Proc. 4th Workshop on Information Theoretic Methods in Science and Engineering (WITSME 2011), Series of Publications C, Report C-2011-45, Department of Computer Science, University of Helsinki, 2011.
- P.M.B. Vitanyi, Compression-based Similarity. In Proc. IEEE 1st Int. Conf. Data Compression, Communication and Processing, Palurno, Italy, June 21-24, 2011, 111--118.
- P. Adriaans, P.M.B. Vitanyi, The power and perils of MDL, Proc. IEEE Intn'l Symp. Information Theory (ISIT), Nice, France, 24-29 June, 2007, 2216-2220.
- L. Antunes, A. Costa, A. Matos and P. Vitanyi, Computational Depth of Infinite Strings Revisited, Proc. CiE 2007, Computation and Logic in the Real World, 2007.
- P.M.B. Vitanyi, Analysis of Sorting Algorithms by Kolmogorov Complexity (A Survey). Pp.209--232 in: In: Entropy, Search, Complexity, Bolyai Society Mathematical Studies, 16, I. Csiszar, G.O.H. Katona, G. Tardos, Eds., Springer-Verlag, 2007.
- R. Cilibrasi, P.M.B. Vitanyi, Automatic extraction of meaning from the web, Proc. IEEE Intn'l Symp. Information Theory (ISIT), Seattle, Wash. USA, 2006, 2309-2313.
- N.K. Vereshchagin, P.M.B. Vitanyi, Algorithmic rate-distortion function, Proc. IEEE Intn'l Symp. Information Theory (ISIT), Seattle, Wash. USA, 2006, 798-802.
- C. Costa Santos, J. Bernardes, P. Vitanyi, L. Antunes, Clustering fetal heart rate tracings by compression, Proc. 19th IEEE Symp. Computer-Based Medical Systems, 2006, 685-690.
- R. Cilibrasi, P.M.B. Vitanyi, Similarity of objects and the meaning of words, Proc. 3rd Conf. Theory and Applications of Models of Computation (TAMC), J.-Y. Cai, S. B. Cooper, and A. Li (Eds.), Lecture Notes in Computer Science, Vol. 3959, Springer-Verlag, Berlin, 2006, 21--45.
- P.M.B. Vitanyi, Time, Space, and Energy in Reversible Computing, Proc. 2005 ACM International Conference on Computing Frontiers, Ischia, Italy, 4-6 May 2005, 435--444.
- P.M.B. Vitanyi, Universal Similarity, Proc. ITW2005 - IEEE ITSOC Information Theory Workshop 2005 on Coding and Complexity, 29th Aug. - 1st Sept., 2005, Rotorua, New Zealand.
- R. Cilibrasi, R. de Wolf, P. Vitanyi, Algorithmic clustering of music, Proc IEEE 4th International Conference on Web Delivering of Music (WEDELMUSIC 2004), IEEE Comp. Soc. Press, 2004, 110-117.
- H. Buhrman, H. Klauck, N.K. Vereshchagin, P.M.B. Vitanyi, Individual communication complexity, Proc. 21st Symp. Theoretical Aspects of Computer Science (STACS), Lecture Notes in Computer Science, Vol. 2996, Springer-Verlag, Berlin, 2004, 19--30.
- N. Vereshchagin and P. Vitanyi, Kolmogorov's Structure Functions with an Application to the Foundations of Model Selection, Proc. 47th IEEE Symp. Found. Comput. Sci. (FOCS'02), 2002, 751-760. Full version click here.
- P.M.B. Vitanyi, Meaningful information, Proc. 13th International Symposium on Algorithms and Computation (ISAAC), Lecture Notes in Computer Science, Vol 2518 Springer-Verlag, Berlin, 2002, 588--599.
- Ming Li, Xin Chen, Xin Li, Bin Ma, Paul Vitanyi, The similarity metric, Proc. 14th ACM-SIAM Symp. Discrete Algorithms (SODA), 2003.
- M. Li, J. Tromp and P.M.B. Vitanyi, Sharpening Occam's razor, Proc. 8th Intn'l Conf. Computing and Combinatorics (COCOON), Lecture Notes in Computer Science, Vol. 2387, Springer-Verlag, Berlin, 2002, 411-419.
- T. Jiang, M. Li, P. Vitanyi, The incompressibility method, Proc. SOFSEM 2000, Lecture Notes in Computer Science, Vol. 1963, Springer-Verlag, Berlin, 2000, 36--53.
- P. Gacs, J. Tromp, P. Vitanyi, Towards and algorithmic statistics, Proc. ALT 2000, Lecture Notes in Artificial Intelligence, Vol. 1968, Springer-Verlag, Berlin, 2000, 41-55.
- P. Vitanyi, Three Approaches to the Quantitative Definition of Information in an Individual Pure Quantum State, Proc. 15th IEEE Conf. Comput. Complexity, 2000.
- Tao Jiang, Ming Li, Paul Vitanyi, The average-case complexity of Shellsort, Proc. ICALP, 1999.
- Tao Jiang, Ming Li, Paul Vitanyi, The expected size of Heilbronn's triangles, Proc. 14th IEEE Conference on Computational Complexity, 1999.
- M. Li and P.M.B. Vitanyi, Average-case analysis via incompressibility, Proc. 11th Conference on Fundamentals of Computation Theory, Lecture Notes in Comuter Science, Vol. 1279, Springer-Verlag, Heidelberg, 1997, 38--50.
- H. Buhrman, M. Li, and P.M.B. Vitanyi, Kolmogorov random graphs, pp. 78--96 in: {\em Proc. IEEE Conference on Compression and Complexity of SEQUENCES 1997}, IEEE Comput. Soc. Press, 1998.
- P.M.B. Vitanyi and M. Li, On Prediction by Data Compression, Proc. 9th European Conference on Machine Learning, Lecture Notes in Artificial Intelligence, Vol. 1224, Springer-Verlag, Heidelberg, 1997, 14-30.
- P.M.B. Vitanyi and M. Li, Ideal MDL and Its Relation To Bayesianism, Proc. ISIS: Information, Statistics and Induction in Science World Scientific, Singapore, 1996, 282-291.
- H. Buhrman, J.H. Hoepman and P.M.B. Vitanyi, Optimal routing tables, Proc. 15th ACM Symp. on Principles of Distributed Computing, 1996, 134-142.
- P.M.B. Vitanyi, Physics and the New Computation, Prague, August 1995, Proc. 20th Int. Symp. Math. Foundations of Computer Science, MFCS'95, Lecture Notes in Computer Science, Vol 969, Springer-Verlag, Heidelberg, 1995, 106-128. (Invited paper)
- P.M.B. Vitanyi and M. Li, Algorithmic arguments in physics of computation, Proc. 4th Workshop on Algorithms and Data Structures, Kingston, Ontario, August 1995, Lecture Notes in Computer Science, Vol 955 Springer-Verlag, Heidelberg, 1995, 315-333. (Invited paper)
- P.M.B. Vitanyi, Multiprocessor architectures and physical law, Proc. 2nd IEEE Workshop on Physics and Computation, PhysComp'94, Dallas (Texas), November 17-20, 1994, pp. 24-29.
- M. Li and P.M.B. Vitanyi, Inductive Reasoning, pp. 127-148 in Language Computations; Proc. DIMACS Workshop on Human Language, March 20-22, 1992, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Volume 17, E.S. Ristad, Ed., American Math. Society, 1994.
- T. Jiang, J. Seiferas and P.M.B. Vitanyi, Two heads are better than two tapes, In: Proc. 26th ACM Symp. Theory of Comput., 1994, 668-675.
- M. Li, Q. Gao and P.M.B. Vitanyi, Recognizing on-line handwritten characters using MDL, Proc. 1993 IEEE Information Theory Workshop, Japan, 1993, 24-25. Manuscript (full version)
- M. Li and P.M.B. Vitanyi, Theories of Learning, In: Proc. Intern. Conf. of Young Computer Scientists, Beijing, China, 1993.
- C.H. Bennett, P. Gacs, M. Li, P.M.B. Vitányi, and W. Zurek, Thermodynamics of Computation and Information Distance, In: Proc. 25th ACM Symp. Theory of Comput., 1993, 21-30.
- M. Li and P.M.B. Vitanyi, Theory of thermodynamics of computation, Proc. IEEE Physics of Computation Workshop, Dallas (Texas), Oct. 4-6, 1992, pp. 42-46. The full version appeared in Preliminary Proceedings Physcomp92.
- M. Li and P.M.B. Vitanyi, Philosophical issues in Kolmogorov complexity, pp. 1-16 in: Proc. International Colloquium on Automata, Languages and Programming, Lecture Notes in Computer Science, Vol. 623, Springer Verlag, Berlin, 1992.
- M. Li and P.M.B. Vitanyi, A brief introduction to Kolmogorov complexity and its applications, in: Chinese Mathematics into the 21st Century, Wu Wen-tsun and Cheng Min-de, Eds, Peking University Press, Peking, China, 1991, pp. 67-84.
- M. Li and P.M.B. Vitanyi, Combinatorics and Kolmogorov complexity, Proc. 6th IEEE Conf. on Structure in Complexity Theory , 1991, pp. 154-163.
- M. Li and P.M.B. Vitanyi, A theory of learning simple concepts under simple distributions Proc. 2nd ACM Workshop on Computational Learning Theory, 1989, p. 386.
- M. Li and P.M.B. Vitanyi, Two applications of the universal distribution , Proc. 1990 AAAI Spring Symposium Series: The Theory and Application of Minimum Length Coding, 1990.
- M. Li and P.M.B. Vitanyi, A theory of learning simple concepts under simple distributions and average case complexity for the universal distribution , Proc. 30th IEEE Symposium on Foundations of Computer Science, 1989, pp. 34-39.
- M. Li and P.M.B. Vitanyi, Inductive reasoning and Kolmogorov complexity , Proc. 4th IEEE Structure in Complexity Theory Conference, 1989, pp. 165-185.
- M. Li and P.M.B. Vitanyi, A new approach to formal language theory by Kolmogorov complexity, Proc. ICALP 89, Lecture Notes in Computer Science , vol. 372, Springer Verlag, 1989, pp. 506-520.
- M. Li and P.M.B. Vitanyi, Two Decades of applied Kolmogorov Complexity: In memoriam Andrei Nikolaevich Kolmogorov 1903 - 1987. In: Proc. 3rd IEEE Structure in Complexity Theory Conference , Washington D.C., 1988, pp. 80-101.
- M. Li, L. Longpr'e, P.M.B. Vitanyi, The power of the queue, Structure in Complexity Theory Conference, Lecture Notes in Computer Science 223, Springer Verlag, Berlin, 1986, 219-233.
Book Articles
- R.L. Cilibrasi and P.M.B. Vitanyi, Normalized Web Distance and Word Similarity, Chapter 13 (pp. 293-314) in: Handbook of Natural Language Processing, Second Edition, Nitin Indurkhya and Fred J. Damerau Eds., Machine Learning and Pattern Recognition Series, Chapman & Hall / CRC Press, Taylor and Francis Group, Boca Raton, FL, 2010, ISBN 978-1420085921.
- P.M.B. Vitanyi, F.J. Balbach, R.L. Cilibrasi, M. Li, Normalized information distance, pp. 45-82 in: Information Theory and Statistical Learning, Eds. F. Emmert-Streib and M. Dehmer, Springer-Verlag, New-York, 2008.
- P. Vitanyi, Algorithmic chaos and the incompressibility method, Pp 301--317 in: Kolmogorov's Heritage of in Mathematics, E. Charpentier, A. Lesne and N.K. Nikolsky, Eds.,Springer-Verlag, Berlin, 2007.
- P.M.B. Vitanyi, Le chaos algorithmique et la methode d'incompressibilite, (Translated in French by Michel Balazard), Chapitre 14, pp. 288--302 in: L'Heritage de Kolmogorov en Mathematique, Editions Belin, Paris, 2004.
- P.D. Gruenwald and P.M.B.Vitanyi, Algorithmic Information Theory, pp. 281-320 in the Handbook of the Philosophy of Information}, P. Adriaans and J. van Benthem, Eds., A volume in the Handbook of the Philosophy of Science, D. Gabbay, P. Thagard, and J. Woods, Eds., North Holland, 2008.
- Marcus Hutter, Shane Legg, Paul M.B. Vitanyi (2007), Algorithmic Probability, Scholarpedia, p. 19046.
- Paul M.B. Vitanyi (2007) Andrey Nikolaevich Kolmogorov. Scholarpedia, p.8546.
- Ming Li, Paul M.B. Vitanyi (2007) Applications of Algorithmic Information Theory. Scholarpedia, p.12407.
- P. Vitanyi, Algorithmic chaos and the incompressibility method, In: The legacy of Kolmogorov in mathematics, Springer Verlag, Berlin, Germany. (In cooperation with Belin Publ., Paris, France.) 2007.
- P.M.B. Vitanyi, Le chaos algorithmique et la methode d'incompressibilite, (Translated from the original English into French by Eric Charpentier), Chapitre 14, pp. 288--302 in: L'Heritage de Kolmogorov en Mathematique, Editions Belin, Paris, 2004.
- P.M.B. Vitanyi, Algorithmic statistics and Kolmogorov's Structure Functions. Pp. 151--174 in: Advances in Minimum Description Length: Theory and Applications, P.D. Grunwald, I.J. Myung, and M.A. Pitt, Eds, MIT Press, 2005.
- P. Vitanyi and M. Li, Simplicity, Information, Kolmogorov Complexity, and Prediction, pp 135--155 in: Simplicity, Inference and Modelling, Arnold Zellner, Hugo A. Keuzenkamp, and Michael McAleer, Eds., Cambridge University Press, Cambridge, UK, 2001/2002.
- M. Li and P.M.B. Vitanyi, Algorithmic Complexity, pp. 376--382 in: International Encyclopedia of the Social & Behavioral Sciences, N.J. Smelser and Paul B. Baltes, Eds., Pergamon, Oxford, 2001/2002.
- T. Jiang, M. Li and P. Vitanyi, Some examples of average-case analysis by the incompressibility method, in {\it Jewels are Forever: Contributions on Theoretical Computer Science in Honor of Arto Salomaa}, J. Karhumaki, H. Maurer, G. Paun, and G. Rozenberg (eds.), Springer, 1999, pp. 250-261.
- M. Li and P.M.B. Vitanyi, Average-Case Analysis Using Kolmogorov Complexity, pp. 157--169 in: Advances in Languages, Algorithms, and Complexity, Ding-Zhu Du and Ker-I Ko Eds., Kluwer Academic Publishers, 1997.
- M. Li and P.M.B. Vitanyi, Computational Machine Learning in Theory and Praxis. In: `Computer Science Today', J. van Leeuwen, Ed., Lecture Notes in Computer Science, Vol. 1000, Springer Verlag, Heidelberg, 1995, 518-535.
- P.M.B. Vitanyi, Randomness. In: `Matematica, Logica, Informatica' Volume 12 of the Storia del XX Secolo, to be published by the Instituto della Enciclopedia Italiana.
- M. Li and P.M.B. Vitanyi, Kolmogorov complexity and its applications, Japanese version, Chapter IV in: Handbook for Theoretical Computer Science, (J. van Leeuwen, Editor), Maruzen Publishing Co., Oyama, Japan, 1994. Translation from the original English into Japanese by O. Watanabe.
- P.M.B. Vitanyi, Randomness. In A.~Schrijver and N.~Temme K.R.~Apt, editor, From Universal morphisms to megabytes: a Baayen space Odyssey, pages 627--642 CWI, Amsterdam, 1994.
- M. Li and P.M.B. Vitanyi, Applications of Kolmogorov Complexity in the theory of computation , pp. 147-203 in: Complexity Theory Retrospective (A.L. Selman, Ed.), Springer Verlag, 1990.
- M. Li and P.M.B. Vitanyi, Kolmogorov complexity and its applications, pp. 187-254 (Chapter IV) in: Handbook for Theoretical Computer Science, (J. van Leeuwen, Editor), Elsevier/MIT Press, 1990. (Also translated in Jpanese and Russian.)
Unpublished and Miscellaneous
- R. Cilibrasi, R. de Wolf, P. Vitanyi, Algorithmic clustering of music, http://arxiv.org/archive/cs/0303025
- P.M.B. Vitanyi, Andrei Nikolaevich Kolmogorov, CWI Quarterly, 1(1988), pp. 3-18.
- P.M.B. Vitanyi, One queue or two pushdown stores take square time on a one-head tape unit. (C.W.I. Report CS-R8406, March 1984)
[Back |Home]
This page is maintained by Paul Vitanyi, at CWI