html>

Chaos

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.

Reversible Computing

P.M.B. Vitanyi, Time, Space, and Energy in Reversible Computing, Proc. 2005 ACM International Conference on Computing Frontiers, (Section: 1st Intnl Workshop on Reversible Computing) Ischia, Italy, 4-6 May 2005, 435--444.
H. Buhrman, J. Tromp, P. Vitanyi, Time and space bounds for reversible simulation, Journal of Physics A: Mathematical and General, 34(2001), 6821--6830.
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, J. Tromp, and P. Vitanyi, Reversible simulation of irreversible computation. Physica D, 120(1998) 168-176.
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.
P.M.B. Vitanyi and M. Li, 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)
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. This is an abstract of the full version in the Preliminary Proceedings of PhysCOMP92, Texas Instruments, Dallas, 1992.
Link to other reversible logic pages .
Link to reversible logic page at MIT .
Link to 1st Intn'l Workshop on Reversible Computing, Ischia, Italy, 2005. .

Quantum Computing

Wiring problems and latency problems in Multicomputers

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.
P.M.B. Vitanyi, Locality, communication and interconnect length in multicomputers, SIAM J. on Computing, 17 (1988), 659-672.
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, 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)
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.

This page is maintained by Paul Vitanyi, at CWI