Publications

Books

M. Li and P.M.B. Vitanyi, Description Complexity and Applications, China Science Press, Beijing, China, 1998 (translation from the original Enlish into Chinese 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)
P.M.B. Vitanyi, Lindenmayer Systems: Structure, Languages, and Growth Functions. MC-Tract 96, Mathematisch Centrum, Amsterdam, 1980. (209 pp, corresponds to Ph. D. Thesis of 1978.)
P.M.B. Vitanyi, Counting: Number Representations and Counter Machine Algorithms. Wiley-Interscience Series in Discrete Mathematics, in preparation.

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.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. DOI: 10.1016/j.tcs.2019.01.031, 2019.
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.
P.M.B. Vitanyi, N. Chater, Algorithmic Identification of Probabilities, Journal of Mathematical Psychology, Volume 76, part A(2017), 13-24.
A.R.Cohen and P.M.B. Vitanyi, Web similarity, Submiited.
A.R.Cohen and P.M.B. Vitanyi, Normalized Compression Distance of Multisets with Applications, IEEE Trans. Pattern Analysis and Machine Intelligence, To Appear. Also arXiv:1212.5711
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
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. 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.
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-34 54
P.M.B. Vitanyi (2009) Turing machine. Scholarpedia, 4(3):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.
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.
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. Vitanyi, Meaningful information, IEEE Trans. Inform. 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.)
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.
R. Cilibrasi, P.M.B. Vitanyi, Automatic meaning discovery using Google. http://xxx.lanl.gov/abs/cs.CL/0412098 (2004)
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.
P.D. Grunwald, P.M.B. Vitanyi, Shannon Information and Kolmogorov complexity, IEEE Trans. Information Theory, Submitted.
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/0312044 (2003)
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, 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.
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)
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.
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.
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.
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, A discipline of evolutionary programming, {\em Theoret. Comp. Sci.}, 241:1-2 (2000), 3--23.
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. Vitanyi, The Erdos graph and the Beast, Mathematical Intelligencer, 21:3(1999), 54--55.
H. Buhrman, M. Franklin, J. Garay, J.H. Hoepman, J. Tromp, P. Vitanyi, Mutual Search, J. Assoc. Comp. Mach., 46:4(1999), 517--536.
H. Buhrman, T. Jiang, M. Li, P. Vitanyi, New applications of the incompressibility method: Part II, Theoretical Computer Science, 235:1(2000), 59--70.
H. Buhrman, M. Li, J. Tromp and P.M.B. Vitanyi, Kolmogorov Random Graphs and the Incompressibility Method, SIAM J. Comput, 29:2(1999), 590--599.
T. Jiang, M. Li, P. Vitanyi, New applications of the incompressibility method, The Computer Journal, 42:4(1999), 287--293.
H. Buhrman, J.H. Hoepman, and P.M.B. Vitanyi, Space-efficient routing tables for almost all networks and the incompressibility method, SIAM J. Comput., 28:4(1999), 1414--1432.
A. Panconesi, M. Papatriantafilou, P. Tsigas, P. Vitanyi, Randomized Naming Using Wait-Free Shared Variables, Distributed Computing, 11(1998), 113--124.
M. Li, J. Tromp, and P. Vitanyi, Reversible simulation of irreversible computation. Physica D, 120(1998) 168-176.
C.H. Bennett, P. Gacs, M. Li, P.M.B. Vitanyi, and W. Zurek, Information Distance, IEEE Trans. Inform. Theory, IT-44:4(1998) 1407--1423.
W. Kirchherr, M. Li and P.M.B. Vitanyi, The miraculous universal distribution, ``Mathematical Intelligencer,'' 19:4(1997), 7--15.
T. Jiang, J. Seiferas and P.M.B. Vitanyi, Two heads are better than two tapes, J. Assoc. Comp. Mach., 44:2(1997), 237--256.
M. Li, J. Tromp and P.M.B. Vitanyi, How to share concurrent wait-free variables, J. Assoc. Comp. Mach., 43 (1996), 723-746.
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.
M. Li and P.M.B. Vitanyi, A new approach to formal language theory by Kolmogorov complexity, SIAM J. Comput., 24:2(1995), 398-410.
M. Li and P.M.B. Vitanyi, Kolmogorov complexity arguments in Combinatorics, J. Comb. Th., Series A, 66:2(1994), 226-236. Correction, Ibid., 69(1995), 183.
M. Li and P.M.B. Vitanyi, Statistical properties of finite sequences with high Kolmogorov complexity, Math. System Theory, 27(1994), 365-376.
M. Li and P.M.B. Vitanyi, Optimality of Wait-Free Atomic Multiwriter Variables, Information Processing Letters, 43(1992), 107-112.
M. Li and P.M.B. Vitanyi, Average case complexity equals worst-case complexity under the Universal Distribution, Information Processing Letters, 42(1992), 145-150.
M. Li, L. Longpré, and P.M.B. Vitanyi, The power of the queue, SIAM J. Computing, 21:4(1992), 697-712.
M. Li and P.M.B. Vitanyi, Inductive reasoning and Kolmogorov complexity, J. Comp. System Sciences, 44:2(1992), 343-384.
E. Kranakis and P.M.B. Vitanyi, A note on weighted distributed Match-Making, Mathematical Systems Theory, 25(1992), 123-140.
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.
P.M.B. Vitanyi, Locality, communication and interconnect length in multicomputers, SIAM J. on Computing, 17 (1988), 659-672.
S.J. Mullender and P.M.B. Vitanyi, Distributed match-making, Algorithmica. 3 (1988), 367-391. (Special `Distributed Computing' issue)
M. Li and P.M.B. Vitanyi, Tape versus stacks and queue: the lower bounds, Information and Computation, 78 (1988), 56-85.
J. Seiferas and P.M.B. Vitanyi, Counting is easy, J. Assoc. Comp. Mach. 35 (1988), pp. 985-1000.
P.M.B. Vitanyi, Square time is optimal for the simulation of one pushdown store or one queue by an oblivious one-head tape unit. Information Processing Letters 21 (1985) 87-91.
P.M.B. Vitanyi, An $O(N^{1.618} )$ lower bound on the time to simulate one queue or two pushdown stores by one tape. Information Processing Letters, 21 (1985) 147-152.
P.M.B. Vitanyi, On two-tape real-time computation and queues, (revised and generally updated IW 139) J. Computer and System Sciences, 29 (1984) 303 - 311.
P.M.B. Vitanyi, On the simulation of many storage heads by one, Theoretical Computer Science, 34 (1984) 157 - 168.
P.M.B. Vitanyi, An optimal simulation of counter machines, SIAM Journal on Computing, 14 (1985), 1-33.
P.M.B. Vitanyi, An optimal simulation of counter machines: the ACM case, SIAM J. on Computing, 14 (1985), 34-40.
W.J. Savitch and P.M.B. Vitanyi, On the power of real-time two-way multihead finite automata with jumps. Information Processing Letters, 19 (1984) 31 - 36.
P.M.B. Vitanyi, On efficient simulations of multicounter machines, Information and Control, 55 (1982) 20 - 39.
P.M.B. Vitanyi, A note on DPDA transductions of \{0,1\}* and inverse DPDA transductions of the Dyck set. International Journal of Computer Mathematics, Section A, 9 (1981), 131 - 137.
P.M.B. Vitanyi and A. Walker, Stable string languages of Lindenmayer systems, Information and Control 37 (1978), 137 - 149.
P.M.B. Vitanyi and W.J. Savitch, On inverse deterministic pushdown transductions, Journal of Computer and System Sciences 16 (1978), 423 - 444.
P. van Emde Boas and P.M.B. Vitanyi, A note on the recursive enumerability of some classes of recursively enumerable sets, Information Sciences 14 (1978), 89 -91.
G.T. Herman and P.M.B. Vitanyi, Growth functions associated with biological development, American Mathematical Monthly 83 (1976), 1 - 15.
P.M.B. Vitanyi, How well can a graph be n -colored?, Discrete Mathematics 34 (1981), 69 - 80.
P.M.B. Vitanyi, Achievable high scores in $\epsilon$-moves and running times in DPDA computation, Information Processing Letters 10 (1980), 83-86.
P.M.B. Vitanyi, Context sensitive table Lindenmayer languages and a relation to the LBA problem, Information and Control 33 (1977), 217 - 226.
P.M.B. Vitanyi, On a problem in the collective behavior of automata, Discrete Mathematics 14 (1976), 99 - 101.
P.M.B. Vitanyi, Deterministic Lindenmayer languages, nonterminals and homomorphisms, Theoretical Computer science 2 (1976), 49 - 71.
P.M.B. Vitanyi, Structure of growth in Lindenmayer systems, Indagationes Mathematicae 35:3 , (1973), 247-253. (is Proc. Koninklijke Nederlandsche Akademie van Wetenschappen, Series A, 76:3(1973).)
P.M.B. Vitanyi, Sexually reproducing cellular automata, Mathematical Biosciences 18 (1973) 23-54.

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, 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.
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, 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.
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.
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. Vitanyi, Meaningful information, Proc. 13th International Symposium on Algorithms and Computation (ISAAC'02), 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. 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.
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.
H. Buhrman, J. Tromp, P. Vitanyi, Time and space bounds for reversible simulation, Journal of Physics A: Mathematical and General, 34(2001), 6821--6830.
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. 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.
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.
H. Buhrman, A. Panconesi, R. Silvestri, and Paul Vitanyi On the importance of having an identity or, is consensus really Universal?, Distributed Computing Conference (DISC'00), Lecture Notes in Computer Science, Vol. 1914, Springer-Verlag, Berlin, 2000, 134--148. Final version published in Distributed Computing Published online: 10 March 2005.
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, in: Proc. ICALP, 1999.
Tao Jiang, Ming Li, Paul Vitanyi, The expected size of Heilbronn's triangles, Proc. 14th IEEE Conference on Computational Complexity, 1999.
H. Buhrman, M. Franklin, J. Garay, J.H. Hoepman, J. Tromp, P. Vitanyi, Mutual Search, Proc. 9th ACM-SIAM Symposium on Discrete Algorithms, 1998.
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, 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.
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.
M. Li and P.M.B. Vitanyi, Reversible simulation of irreversible computation, Proc. 11th IEEE Conference on Computational Complexity, 1996, 301-306.
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.
A. Panconesi, M. Papatriantafilou, P. Tsigas, P. Vitanyi, Randomized Wait-Free Distributed Naming, Proc. Fifth Annual International Symposium on Algorithms and Computation, Beijing, Springer Lecture Notes in Computer Science, Volume 834, 1994, pp 83-91. (Semi-final version)
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.
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)
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.
Y. Afek, E. Gafni, J. Tromp, P.M.B. Vitanyi, Wait-free test-and-set, pp. 85-94 in: Proc. 6th Workshop on Distributed Algorithms (WDAG-6), Lecture Notes in Computer Science, vol. 647, Springer Verlag, Berlin, 1992.
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, How to share concurrent asynchronous wait-free variables, Proc. ICALP 89, Lecture Notes in Computer Science , vol. 372, Springer Verlag, 1989, pp. 488-505.
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.
E. Kranakis and P.M.B. Vitanyi, Weighted distributed Match-Making, Proceedings AWOC '88, Lecture Notes in Computer Science, vol. 319, Springer Verlag, Berlin, 1988, pp. 361-368.
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.
B. Awerbuch, L. Kirousis, E. Kranakis and P.M.B. Vitanyi, A proof technique for register atomicity, In: Proc. 8th Conf. Found. Software Techn. and Theoret. Comp. Sci., Lecture Notes in Computer Science, vol. 338, Springer Verlag, Berlin, 1988, pp. 286-303.
L. Kirousis, E. Kranakis and P.M.B. Vitanyi, Atomic multireader register, Proceedings 2nd International Workshop on Distributed Algorithms, Lecture Notes in Computer Science, Vol 312, Springer Verlag, Berlin, 1987, pp. 278-296.
P.M.B. Vitanyi and B. Awerbuch, Atomic shared register access by asynchronous hardware, Proceedings 27th Annual IEEE Symposium on Foundations of Computer Science, 1986, 233-243. Errata, FOCS'87. The Peterson-Burns's fix in their paper in FOCS'87 is erroneous as pointed out by Haldar and Vidyasankar in a report, see history in the Haldar-Vitanyi paper below. The problem in the errata is resolved by M. Li, J. Tromp and P.M.B. Vitanyi, How to share concurrent wait-free variables, J. Assoc. Comp. Mach., 43 (1996), 723-746. giving an optimal wait-free atomic multiwriter multireader register from wait-free atomic 1-writer 1-reader registers using bounded timestamps (by projections of the method also wait-free atomic multiwriter multireader register from wait-free atomic 1-writer multireader register, and wait-free atomic 1-writer multireader register from wait-free atomic 1-writer 1-reader register). It turns out that the method in the Vitanyi-Awerbuch original bounded multiwriter system (made error-free) is strong enough to implement a concurren bounded timestamp system from wait-free atomic 1-writer multireader registers S. Haldar and P. Vitanyi, Bounded concurrent timestamp systems using vector clocks, J. Assoc. Comp. Mach., 49:1(2002), 101-126.
P.M.B. Vitanyi, Non-sequential computation and Laws of Nature, In: VLSI Algorithms and Architectures (Proceedings Aegean Workshop on Computing, 2nd International Workshop on Parallel Processing and VLSI), Lecture Notes In Computer Science 227, Springer Verlag, 1986, 108-120. (Invited)
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.
S.J. Mullender and P.M.B. Vitanyi, Distributed match-making for processes in computer networks. In: Proceedings 4th ACM Symposium on Principles of Distributed Computing , 1985, 261-271. Reprinted in Operating Systems Review , 1986.
P.M.B. Vitanyi, Area penalty for sublinear signal propagation delay on chip, Proceedings 26th Annual IEEE Symposium on Foundations of Computer Science , 1985, 197-207.
P.M.B. Vitanyi, The simple roots of real-time computation hierarchies (preliminary draft). 11th International Colloquium on Automata, Languages and Programming, Lecture Notes in Computer Science 172, Springer Verlag, Berlin, 1984, 486 - 489.
P.M.B. Vitanyi, Distributed elections in an Archimedean ring of processors (preliminary draft). 16th ACM Symposium on Theory of Computing, Washington D.C., 1984, 542 - 547
P.M.B. Vitanyi, On the simulation of many storage heads by a single one (extended abstract). In: Proceedings 10th International Colloquium on Automata, Languages and Programming (ICALP '83), Lecture Notes in Computer Science 154, Springer Verlag, Berlin, 1983, 687 - 694.
P.M.B. Vitanyi, Real-time simulation of multicounter machines by oblivious one-tape Turing machines. In: Proceedings 14th ACM Symposium on Theory of Computing , 1982, 27-36.
P.M.B. Vitanyi, Efficient simulations of multicounter machines, extended abstract. In: Proceedings 9th International Colloquium on Automata, Languages and Programming (ICALP '82), Lecture Notes in Computer Science 140 , Springer Verlag, Berlin, 1982, 546 - 560.
P.M.B. Vitanyi, On the power of real-time Turing machines under varying specifications, extended abstract. In: Proc. Int. Coll. Automata, Languages and Programming (ICALP '80), Lecture Notes in Computer science 85 , Springer Verlag, Berlin, 1980, 658 - 671.
P.M.B. Vitanyi, Relativized obliviousness. In: Proc. Symp. Math. Fund. Comp. Sci (MFCS '80), Lecture Notes in Computer Science 88 , Springer Verlag, Berlin, 1980, 665 - 672.
W.J. Savitch and P.M.B. Vitanyi, Linear time simulation of multihead Turing machines with head-to-head jumps. In: Proc. 4th International Colloquium on Automata, Languages and Programming (ICALP), Lecture Notes in Computer Science 52 , Springer Verlag, Berlin, 1977, 453 - 464.
P.M.B. Vitanyi, Digraphs associated with DOL systems. In: A. Lindenmayer and G. Rozenberg Eds., Automata, Languages, Development. North-Holland, Amsterdam, 1976, 335 - 346.
P.M.B. Vitanyi, On the size of DOL-languages. In: G. Rozenberg and A. Salomaa Eds., L-Systems, Lecture Notes in Computer Science 15 , Springer Verlag, Berlin, 1974, 78 - 92.
P.M.B. Vitanyi, Growth of strings in context dependent L-Systems. In: G. Rozenberg and A. Salomaa Eds., L-Systems, Lecture Note in Computer Science 15 , Springer Verlag, Berlin, 1974, 104 - 123.
P.M.B. Vitanyi, Genetics of reproducing automata. In: Proc. 1974 Conference on Biologically Motivated Automata Theory, IEEE, New York, N.Y., 1974, 166-171.

Book Articles

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.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.
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, 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.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,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.
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.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.
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.
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.
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.
P.M.B. Vitanyi, A tour of Algorithmics, pp. 337-348 in: Images of SMC Research 1996, W.A.M. Aspers, J.W. de Bakker, P.J.W. ten Hagen, M. Hazewinkel, P.J. van der Houwen, and H.M. Nieuwland, eds., Stichting Mathematisch Centrum, Amsterdam, 1996.
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.)
P.M.B. Vitanyi, ``A modest proposal for communication costs in multicomputers,'' pp. 203-216 in: Concurrent Computations, Algorithms, Architecture, and Technology, (S.K. Tewksbury, B.W. Dickinson and S.C. Schwartz, eds.), Plenum Press, New York, 1988.
P.M.B. Vitanyi, Algorithmics or Algotecture?, In: Mathematics and Computer Science II, CWI Monographs, Volume 4, (M. Hazewinkel, J.K. Lenstra and L.G.L.T. Meertens, Eds.) North-Holland, 1986, pp 139-161.
P.M.B. Vitanyi, Development, Growth and Time. In: The Book of L, G. Rozenberg and A. Salomaa, Eds., Springer Verlag, Berlin, 1985, 431-444.

Edited Books

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.
G. Tel and P.M.B. Vitanyi, Eds., Distributed Algorithms, Proc. 8th International Workshop, WDAG'94, Lecture Notes in Computer Science, Volume 857, Springer-Verlag, Heidelberg, 1994.

Unpublished and Miscellaneous

A. Israeli, M. Li and P.M.B. Vitanyi, Simple multireader registers using timestamp systems, CWI Tech. Rept. CS-R8758.
J. Tromp and P.M.B. Vitanyi, A randomized algorithm for two-process wait-free test-and-set, under revision for a technical journal.
P.M.B. Vitanyi, Andrei Nikolaevich Kolmogorov, CWI Quarterly, 1(1988), pp. 3-18.
M.P.M. van de Ven and P.M.B. Vitanyi, Een marktgerichte aanpak van de structurele werkeloosheid, Economisch Statistische Berichten 73(1988), pp. 1001-1004, 1010. (In Dutch)
M. Li and P.M.B. Vitanyi, A very simple construction for atomic multiwriter register, Tech. Rept. TR-8701, Aiken Computation Laboratory, Harvard University, November 1987.
P.M.B. Vitanyi, Time-driven algorithms for distributed control, CWI Report CS-R8510
P.M.B. Vitanyi, Counting is easy (An essay at the occasion of Arjen Lenstra's Doctorate in the Mathematical and Physical Sciences). In: Dopo le Parole, H.W. Lenstra, Jr., J.K. Lenstra and P. van Emde Boas, Eds., Private Edition, Amsterdam, 1984.
P.M.B. Vitanyi and L. Meertens, Big Omega versus the wild functions, Bulletin of the European Association for Theoretical Computer Science (EATCS) 22(1984), 14 -19. Also in: SIGACT News, 16:4 (1985) 56-59.
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)
P.M.B. Vitanyi, On Generalized Cellular Automata and Sexually Reproducing Cellular Automata. Masters Thesis, Dept. of Mathematics, Technological University of Delft, 1971. (117 pp.)

This page is maintained by Paul Vitanyi, at CWI and was last modified on January 24, 1996.