Books and Edited Books

• P.M.B. Vitanyi, Counting: Number Representations and Counter Machine Algorithms. Wiley-Interscience Series in Discrete Mathematics, in preparation.

Journal Articles

• P.M.B. Vitanyi, On the average-case complexity of Shellsort, Random Structures and Algorithms, 52:2(2018), 354-363.
• 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, Exact Expression for Information Distance, IEEE Trans. Inform. Theory, 63:8(2017), 4725-4728.
• P.M.B. Vitanyi, N. Chater, Algorithmic Identification of Probabilities, Journal of Mathematical Psychology}, Volume 76, part A(2017), 13-24.
• P.M.B. Vitanyi, Turing machines and understanding computational complexity. In: S. Barry Cooper, Jan van Leeuwen (eds.), {\em Alan Turing: His Work and Impact}, Elsevier, Amsterdam, London, New York, Tokyo, 2013, pp.57-63.
• R. Cilibrasi, P.M.B. Vitanyi, A fast quartet tree heuristic for hierarchical clustering, Pattern Recognition, 44 (2011) 662-677.
• S.A. Terwijn, L. Torenvliet, and P.M.B. Vitanyi, Nonapproximablity of the Normalized Information Distance, Journal of Computer and System Sciences, 77(2011), 738-742.
• P.M.B. Vitanyi (2009) Turing machine. Scholarpedia, 4(3):6240.
• H. Buhrman, H. Klauck, N.K. Vereshchagin, P.M.B. Vitanyi, Individual communication complexity, J. Comput. Syst. Sci. 73(2007), 973--985.
• T. Jiang, M. Li, and P. Vitanyi, The average-case area of Heilbronn-type triangles, Random Structures and Algorithms, 20:2(2002), 206-219.
• 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, A lower bound on the average-case complexity of Shellsort, J. Assoc. Comp. Mach., 47:5(2000), 905--911.
• 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, Theretical 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(2000), 590--599.
• T. Jiang, M. Li, P. Vitanyi, New applications of the incompressibility method, The Computer Journal, 42:4(1999), 287--293.
• M. Li, J. Tromp, and P.M.B. Vitányi, Reversible Simulation of Irreversible Computation, Physica D, 120(1998) 168-176.
• 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 and P.M.B. Vitányi, 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. Vitányi, A new approach to formal language theory by Kolmogorov complexity, SIAM J. Comput., 24:2(1995), 398-410.
• M. Li and P.M.B. Vitányi, 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. Vitányi, The power of the queue, SIAM J. Computing, 21:4(1992), 697-712.
• M. Li and P.M.B. Vitányi, Tape versus stacks and queue: the lower bounds, Information and Computation, 78 (1988), 56-85.
• J. Seiferas and P.M.B. Vitányi, Counting is easy, J. Assoc. Comp. Mach. 35 (1988), pp. 985-1000.
• 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. Vitányi, 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. Vitányi, 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. Vitányi, On two-tape real-time computation and queues, J. Computer and System Sciences, 29 (1984) 303 - 311.
• P.M.B. Vitányi, 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. Vitányi, On efficient simulations of multicounter machines, Information and Control, 55 (1982) 20 - 39.
• P.M.B. Vitányi, A note on DPDA transductions of \{0,1\}* and inverse DPDA transductions of the Dyck set. International Journal of Computer Mathematics, Section A, 9
• P.M.B. Vitányi, How well can a graph be n -colored?, Discrete Mathematics 34 (1981), 131 - 137.
• P.M.B. Vitányi 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. Vitányi, A note on the recursive enumerability of some classes of recursively enumerable sets, Information Sciences 14 (1978), 89 -91.
• P.M.B. Vitányi, Achievable high scores in $\epsilon$-moves and running times in DPDA computation, Information Processing Letters 10 (1980), 83-86.

Conference Articles

• 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, A New Quartet Tree Heuristic for Hierarchical Clustering, EU-PASCAL Statistics and Optimization of Clustering Workshop, 5-6 Juli 2005, London, UK.
• 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.
• 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.
• Tao Jiang, Ming Li, Paul Vitanyi, The average-case complexity of Shellsort, To appear 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. Vitányi, 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. Vitányi, Kolmogorov random graphs, pp. 78--96 in: {\em Proc. IEEE Conference on Compression and Complexity of SEQUENCES 1997}, IEEE Comput. Soc. Press, 1998.
• M. Li and P.M.B. Vitányi, Reversible simulation of irreversible computation, Proc. 11th IEEE Conference on Computational Complexity, 1996.
• T. Jiang, J. Seiferas and P.M.B. Vitányi, Two heads are better than two tapes, In: Proc. 26th ACM Symp. Theory of Comput., 1994, 668-675.
• C.H. Bennett, P. Gács, 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. Vitányi, 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. Vitányi, 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. Vitányi, 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, L. Longpr'e, P.M.B. Vitányi, The power of the queue, Structure in Complexity Theory Conference, Lecture Notes in Computer Science 223, Springer Verlag, Berlin, 1986, 219-233.
• P.M.B. Vitányi, 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. Vitányi, 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. Vitányi, 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. Vitányi, 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. Vitányi, 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. Vitányi, 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. Vitányi, 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.

Book Articles

• M. Li, P. Vitanyi, Applications of Algorithmic Information Theory, http://www.scholarpedia.com/article/Applications_of_Algorithmic_Information_Theory
• P. Vitanyi, Registers. Entry in: Encyclopedia of Algorithms, Ming-Yang Kao, Ed., Springer, To appear.
• 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, 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, 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.

Unpublished and Miscellaneous

• 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)

[Back |Home]