A Selection of Recent Publications

• 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.01222
• 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, How incomputable is Kolmogorov complexity? Entropy 2020, 22, 408; doi:10.3390/e22040408
• P.M.B.Vitanyi, Logical depth for reversible Turing machines with an application to the rate of decrease in logical depth for general Turing machines, Theor. Comput. Sci., 778(2019), 78-80.
• P.M.B.Vitanyi, Correction to: “On the Rate of Decrease in Logical Depth,” Theor. Comput. Sci., 702(2017), 60–64, by L.F. Antunes, A. Souto, and P.M.B. Vitányi.
• P.M.B. Vitanyi, On the average-case complexity of Shellsort, Random Structures and Algorithms, 52:2(2018), 354-363.
• P.M.B. Vitanyi, Exact Expression for Information Distance, IEEE Trans. Inform. Theory, 63:8(2017), 4725-4728.
• L.F. Antunes, A. Souto, and P.M.B. Vitanyi, On the rate of decrease in logical depth, Theoret. Comput. Sci., 702(2017), 60-64.
• A.R.Cohen and P.M.B. Vitanyi, Web similarity, Submitted. Also arXiv 1502.05957
• A.R.Cohen and P.M.B. Vitanyi, Normalized Compression Distance of Multisets with Applications, IEEE Trans. Pattern Analysis and Machine Intelligence, 37:8(2015), 1602--1614.
• P.M.B. Vitanyi, Tolstoy's mathematics in ``War and Peace,'' Mathematical Intelligencer, 35:1(2013), 71-75; DOI 10.1007/s00283-012-9342-8
• P.M.B. Vitanyi, N. Chater, Algorithmic 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, Conditional Kolmogorov complexity and Universal probability, Theoretical Computer Science 501(2013) 93-100.
• 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
• 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.M.B. Vitanyi: Turing machines and understanding computational complexity. In: S. Barry Cooper, Jan van Leeuwen (eds.), "Alan Turing: His Work and Impact", Elsevier, Amsterdam, London, New York, Tokyo, 2013, pp.57-63.
• P. Gacs, P.M.B. Vitanyi, Raymond J. Solomonoff 1926–2009, IEEE Information Theory Society Newsletter, 61:1(2011), 11-16.
• 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.
• P.M.B. Vitanyi, Remembering Kolmogorov: Review of ``Kolmogorov in Perspective, Vol. 20 of History of Mathematics, Amer. Math. Soc. / London Math. Soc. 2000, repr. 2006'', Metascience, Springer, 20(2011), 509–511. DOI 10.1007/s11016-011-9540-6.
• 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.
• P.M.B. Vitanyi, Obituary: Ray Solomonoff, Founding Father of Algorithmic Information Theory, Algorithms, 3:3(2010), 260-264
• 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-3454.
• 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., Chapman & Hall / CRC Press Machine Learning and Pattern Recognition Series, Boca Raton, FL, 2010, ISBN 978-1420085921.
• P.M.B. Vitanyi, Turing machine. Scholarpedia, 4:3(2009), 6240.
• E.G. Daylight, W.M. Koolen, P.M.B. Vitanyi, On time-bounded incompressibility of compressible strings and sequences, Information Processing Letters, 109:18(2009), 1055-1059.
• P. Adriaans, P.M.B. Vitanyi, Approximation of the two-part MDL code, IEEE Trans. Inform. Theory, 55:1(2009), 444--457.
• L. Antunes, A. Matos, A. Souto and P. Vitanyi, Depth as Randomness Deficiency, Theory of Computing Systems, 45:4(2009), 724-739.
• M. Li and P.M.B. Vitanyi, An Introduction to Kolmogorov Complexity and its Applications, Springer-Verlag, New York, Third Edition, 2008 (xxiii+790pp)
• 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.M.B. Vitanyi, A great mind, pp 305-309 in: Festschrift in Honor of Jorma Rissanen in the Occasion of his 75th Birthday, P. Grunwald, P. Myllymaki, I. Tabus, M. Weinberger, B. Yu, Eds., Tampere Int. Center for Signal Processing, TICSP Series #38, Tampere Univ. of Technology, Tampere, Finland, 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,Tolsztoj matematikája a "Háború és béké"-ben, (in Hungarian) Ponticulus Hungaricus, XI. évfolyam 4. szám ▪ 2007. április, Hungarian translation © Könyves Tóth Pál, 2007.
• 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.
• 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.
• 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.
• H. Buhrman, H. Klauck, N.K. Vereshchagin, P.M.B. Vitanyi, Individual communication complexity, J. Comput. Syst. Sci. 73(2007), 973--985.
• R.L. Cilibrasi, P.M.B. Vitanyi, The Google Similarity Distance, IEEE Trans. Knowledge and Data Engineering, 19:3(2007), 370-383.
• 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.
• 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, http://www.scholarpedia.com/article/Applications_of_Algorithmic_Information_Theory
• P.M.B. Vitanyi, Registers, Encyclopedia of Algorithms, Ming-Yang Kao, Ed., Springer, 2008, Part 17, 10.1007/978-0-387-30162-4_338.
• R. Cilibrasi, Z. Lotker, A. Navarra, S. Perennes, P. Vitanyi,` About the lifespan of peer to peer networks, Proc. 10th Int'nl Conf. Principles Of Distributed Systems (OPODIS), Lecture Notes in Computer Science, Vol. 4305, Springer Verlag, Berlin, 2006, 290--305.
• 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. Vitanyi, Meaningful information, IEEE Trans. Inform. Th.,52:10(2006), 4617 - 4626.
• 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.)
• 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.M.B. 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, 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, P.M.B. Vitanyi, Automatic meaning discovery using Google. http://xxx.lanl.gov/abs/cs.CL/0412098 (2004)
• N.K. Vereshchagin, P.M.B. Vitanyi, Algorithmic rate-distortion theory, http://arxiv.org/abs/cs.IT/0411014, Submitted.
• P.D. Grunwald, P.M.B. Vitanyi, Shannon Information and Kolmogorov complexity, IEEE Trans. Information Theory, Submitted.
• H. Buhrman, A. Panconesi, R. Silvestri, and Paul Vitanyi On the importance of having an identity or, is consensus really Universal?, Distributed Computing, 18(2006), 167--176.
• R. Cilibrasi, P.M.B. Vitanyi, Clustering by compression, IEEE Trans. Information Theory, 51:4(2005), 1523- 1545. Also: http://xxx.lanl.gov/abs/cs.CV/031204 (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.
• N.K. Vereshchagin and P.M.B. Vitanyi, Kolmogorov's Structure functions and model selection, IEEE Trans. Inform. Theory, 50:12(2004), 3265- 3290.
• 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.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.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. 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.
• N. Chater and P. Vitanyi, Simplicity: A unifying principle in cognitive science? Trends in Cognitive Sciences, 7:1(2003), 19--22.
• P. Vitanyi, Simple wait-free multireader registers, Proc 16th Intn'l Symp. Distributed Computing (DISC'02), Lecture Notes in Computer Science, Vol. 2508, Springer-Verlag, Berlin, 2002, 118--132.
• H. Diederik, P.P.H. Le Brun, H.W. Frijlink, P.M.B. Vitanyi, M. Weda, D.M. Barends, Drug output of unvented jet nebulizers as a function of time. {\em International Journal of Pharmaceutics}, 257:1-2(2003), 33--39.
• M. Li, J. Tromp and P.M.B. Vitanyi, Sharpening Occam's razor, Information Processing Letters, 85:5(2003), 267--274.
• 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.
• 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.
• T. Jiang, M. Li, and P. Vitanyi, The average-case area of Heilbronn-type triangles, Random Structures and Algorithms, 20:2(2002), 206-219.
• S. Haldar and P. Vitanyi, Bounded concurrent timestamp systems using vector clocks, J. Assoc. Comp. Mach., 49:1(2002), 101-126.
• J. Tromp and P. Vitanyi, Randomized two-process wait-free test-and-set, Distributed Computing, 15(2002), 127--135. Construction validation with the PRISM checker at the University of Birmingham (UK)
• K. Amano, J. Tromp, P. Vitanyi, and O. Watanabe, On a generalized ruin problem, Proc. RANDOM-APPROX 2001, Lecture Notes in Computer Science, Vol. 2129, Springer-Verlag, Berlin, 2001, 181-191.
• 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.
• P. Vitanyi, Quantum Kolmogorov complexity using classical descriptions, IEEE Trans. Inform. Theory, 47:6(2001), 2464-2479.
• H. Buhrman, J. Tromp, P. Vitanyi, Time and space bounds for reversible simulation, Journal of Physics A: Mathematical and General, 34(2001), 6821--6830.
• P. Vitanyi, The quantum computing challenge, pp. 219--233 in: Informatics: 10 Years Back, 10 Years Ahead, Lecture Notes in Computer Science, Vol. 2000, Springer Verlag, Berlin.
• Q. Gao, M. Li and P.M.B. Vitanyi, Applying MDL to learning best model granularity, Artificial Intelligence, 121:1-2(2000), 1--29.
• T. Jiang, M. Li, and P. Vitanyi, A lower bound on the average-case complexity of Shellsort, J. Assoc. Comp. Mach., 47:5(2000), 905--911.
• 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.
• T. Jiang, M. Li, and P. Vitanyi, Average-case analysis of algorithms using Kolmogorov complexity, {\em Journal of Computer Science and Technology}, 15:5(2000), 402--408.
• H. Buhrman, M. Franklin, J. Garay, J.H. Hoepman, J. Tromp, P. Vitanyi, Mutual Search, J. Assoc. Comp. Mach., 46:4(1999), 517--536.
• P. Vitanyi, The Erdos graph and the Beast, Mathematical Intelligencer, 21:3(1999), 54--55.
• H. Buhrman, T. Jiang, M. Li, P. Vitanyi, New applications of the incompressibility method: Part II, Theoretical Computer Science, 235:1(2000), 59--70.
• P.M.B. Vitanyi, A discipline of evolutionary programming, {\em Theoret. Comp. Sci.}, 241:1-2 (2000), 3--23.
• H. Buhrman, M. Li, J. Tromp and P.M.B. Vitanyi, Kolmogorov Random Graphs and the Incompressibility Method, SIAM J. Comput, 29:2(2000), 590--599.

---

Click here for a larger selection.