Books and Edited Books

• M. Li and P.M.B. Vitanyi, Description Complexity and Applications, China Science Press, Beijing, China, 1998 (in Chinese).
• M. Li and P.M.B. Vitanyi, An Introduction to Kolmogorov Complexity and its Applications, Springer-Verlag, New York, Second Edition, 1997 (xx+637pp).
• P.M.B. Vitanyi, Ed., Proc. 2nd European Conference on Computational Learning Theory, EuroCOLT'95, Lecture Notes in Artificial Intelligence (A subseries of Lecture Notes in Computer Science), Volume 904, Springer-Verlag, Heidelberg, 1995.

Journal Articles

• A.R. Cohen and P.M.B. Vitanyi, The cluster structure function, IEEE Trans. Pattern Analysis and Machine Intelligence, 45:9(2023), 11309--11320. Also arXiv:2201.01222, https://doi.org/10.48550/arXiv.2201.0122
• R.L. Cilibasi and P.M.B. Vitanyi, Fast phylogeny of SARS-CoV-2 by compression, Entropy 24:4(2022) 439. https://doi.org/10.3390/e24040439
• A.R. Cohen and P.M.B. Vitanyi, Web similarity in sets of search terms using database queries, SN Computer Science (2020) 1:161 https://doi.org/10.1007/s42979-020-00148-5
• P.M.B. Vitanyi, Exact Expression for Information Distance, IEEE Trans. Inform. Theory, 63:8(2017), 4725-4728.
• A.R.Cohen and P.M.B. Vitanyi, Web similarity, Submitted.
• A.R.Cohen and P.M.B. Vitanyi, Normalized Compression Distance of Multisets with Applications, IEEE Trans. Pattern Analysis and Machine Intelligence, Machine Intelligence, 37:8(2015), 1602--1614.
• P.M.B. Vitanyi, N. Chater, Identification of Probabilities, Journal of Mathematical Psychology, Volume 76, part A(2017), 13-24.
• A.S. Hsu, N. Chater, P.M.B. Vitanyi, Language learning from positive evidence, reconsidered: A simplicity-based approach. Topics in Cognitive Science, 5:1(2013), 35-55.
• P.M.B. Vitanyi, Similarity and denoising, Philosophical Transactions of the Royal Society, A, 371(2013), 20120091, http://dx.doi/org/10.1098/rsta.2012.0091
• S. de Rooij, P. Vitanyi, Approximating rate-distortion graphs of individual data: Experiments in lossy compression and denoising, IEEE Trans. Comp., 61:3(2012), 395-407.
• P.M.B. Vitanyi, Information distance in multiples, IEEE Trans. Inform. Theory, 57:4(2011), 2451-2456.
• R. Cilibrasi, P.M.B. Vitanyi, A fast quartet tree heuristic for hierarchical clustering, Pattern Recognition, 44 (2011) 662-677.
• A.S. Hsu, N. Chater, P.M.B. Vitanyi, The probabilistic analysis of language acquisition: Theoretical, computational, and experimental analysis, Cognition, 120(2011), 380-390.
• S.A. Terwijn, L. Torenvliet, and P.M.B. Vitanyi, Nonapproximability of the Normalized Information Distance, J. Comput. System Sciences, 77:4(2011), 738-742.
• N.K. Vereshchagin and P.M.B. Vitanyi, Rate distortion and denoising of individual data using Kolmogorov complexity, IEEE Trans. Information Theory, 56:7(2010), 3438-34 54.
• P. Adriaans, P.M.B. Vitanyi, Approximation of the two-part MDL code, IEEE Trans. Inform. Theory, 55:1(2009), 444--457.
• 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.
• N. Chater, P.M.B. Vitanyi, `Ideal learning' of natural language: Positive results about learning from positive evidence, Journal of Mathematical Psychology, 51:3(2007), 135-163.
• R.L. Cilibrasi, P.M.B. Vitanyi, The Google Similarity Distance, IEEE Trans. Knowledge and Data Engineering, 19:3(2007), 370-383.
• P. Vitanyi, Asshuku ni Motozuita Hanyou na Ruijido Sokuteihou, Surikagaku, No. 519, Sept. 2006, 54--59. (Japanese, translated by O. Watanabe, English title: Universal similarity based on compression.)
• P. Vitanyi, Meaningful information, IEEE Trans. Inform. Th., 52:10(2006), 4617 - 4626.
• R. Cilibrasi, P.M.B. Vitanyi, Automatic meaning discovery using Google, http://xxx.lanl.gov/abs/cs.CL/0412098 (2004).
• P.D. Grunwald, P.M.B. Vitanyi, Shannon Information and Kolmogorov complexity, IEEE Trans. Information Theory, Submitted.
• N.K. Vereshchagin and P.M.B. Vitanyi, Kolmogorov's Structure functions and model selection, IEEE Trans. Inform. Theory, 50:12(2004), 3265- 3290.
• R. Cilibrasi, P.M.B. Vitanyi, Clustering by compression, IEEE Trans. Inform. Theory, 51:12(2005), 1523- 1545. Also http://xxx.lanl.gov/abs/cs.CV/0312044 (2003).
• R. Cilibrasi, P.M.B. Vitanyi, R. de Wolf, Algorithmic clustering of music based on string compression, Computer Music J., 28:4(2004), 49-67.
• M. Li, X. Chen, X. Li, B. Ma, P.M.B. Vitanyi, The similarity metric, IEEE Trans. Inform. Th., 50:12(2004), 3250- 3264.
• P.D. Grunwald and P.M.B. Vitanyi, Kolmogorov complexity and information theory. With an interpretation in terms of questions and answers. J. Logic, Language, and Information, 12:4(2003), 497--529.
• N. Chater, P.M.B. Vitanyi, The generalized universal law of generalization, Journal of Mathematical Psychology, 47:3(2003), 346--369.
• M. Li, J. Tromp and P.M.B. Vitanyi, Sharpening Occam's razor, Information Processing Letters, 85:5(2003), 267--274.
• N. Chater and P. Vitanyi, Simplicity: A unifying principle in cognitive science? Trends in Cognitive Sciences, 7:1(2003), 19--22.
• N. Chater, P.M.B. Vitanyi, N. Steward, Universal generalization and universal inter-item confusability, Behavior and Brain Sciences, 24:4(2001), 559--660.
• P. Gacs, J. Tromp, P. Vitanyi, Algorithmic statistics, IEEE Trans. Inform. Theory, 47:6(2001), 2443-2463.
• Q. Gao, M. Li and P.M.B. Vitanyi, Applying MDL to learning best model granularity, Artificial Intelligence, 121:1-2(2000), 1--29.
• P.M.B. Vitanyi and M. Li, Minimum Description Length Induction, Bayesianism, and Kolmogorov Complexity, IEEE Trans. Inform. Theory, IT-46:2(2000), 446--464.
• P.M.B. Vitanyi, A discipline of evolutionary programming, {\em Theoret. Comp. Sci.}, 241:1-2 (2000), 3--23.
• C.H. Bennett, P. Gacs, M. Li, P.M.B. Vitányi, and W. Zurek, Information Distance, IEEE Trans. Inform. Theory, IT-44:4(1998) 1407--1423.
• M. Li and P.M.B. Vitanyi, Reversibility and adiabatic computation: trading time and space for energy, Proc. Royal Society of London, Series A, 452(1996), 769-789. Section 3.1 and especially Theorem 2 form the basis and is a forerunner of the paper ``Information Distance'' above.
• W. Kirchherr, M. Li and P.M.B. Vit\'anyi, The miraculous universal distribution, ``Mathematical Intelligencer,'' 19:4(1997), 7--15.
• M. Li and P.M.B. Vitanyi, Inductive reasoning and Kolmogorov complexity, J. Comp. System Sciences, 44:2(1992), 343-384.
• M. Li and P.M.B. Vitanyi, Learning simple concepts under simple distributions, SIAM. J. Computing, 20:5(1991), 911-935.
• M. Li and P.M.B. Vitanyi, Kolmogorovskaya slozhnost': dvadsat' let spustia, Uspekhi Mat. Nauk , 43:6 (1988), pp. 129-166. (= Russian Mathematical Surveys ) Translated from the original English into Russian by A.Kh. Shen and N.K. Vereshchagin.

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.
• 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.
• R. Cilibrasi, P.M.B. Vitanyi, A New Quartet Tree Heuristic for Hierarchical Clustering, EU-PASCAL Statistics and Optimization of Clustering Workshop, 5-6 Juli 2005, London, UK.
• 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.
• N.K. Vereshchagin, P.M.B. Vitanyi, Algorithmic rate-distortion theory, http://arxiv.org/abs/cs.IT/0411014, Submitted.
• 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.
• 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.
• 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.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, Genetic fitness optimization using rapidly mixing Markov chains, Proc. 7th Int'nl Workshop on Algorithmic Learning Theory, Lecture Notes in Artificial Intelligence, Vol. 1160, Springer-Verlag, Heidelberg, 1996, 67-82.
• 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.
• 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.
• G. te Brake, J.N. Kok, and P.M.B. Vitanyi, Model selection for neural networks: comparing MDL and NIC. In: Proc. European Symposium on Artificial Neural Networks, Brussels, April 20-22, 1994.
• 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)
• 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, Theories of Learning, In: Proc. Intern. Conf. of Young Computer Scientists, Beijing, China, 1993.
• 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, 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, 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.

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.
• M. Li, P. Vitanyi, Applications of Algorithmic Information Theory, http://www.scholarpedia.com/article/Applications_of_Algorithmic_Information_Theory
• 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, 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.
• 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, 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.
• 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 Japanese by O. Watanabe, and into Russian by A.Kh. Shen and N.K. Vereshchagin.)

[Back |Home]