| 2007 | ISIT | The Power and Perils of MDL. | Pieter W. Adriaans, Paul M. B. Vitnyi |
| 2006 | CBMS | Clustering Fetal Heart Rate Tracings by Compression. | Cristina Costa-Santos, Joo Bernardes, Paul M. B. Vitnyi, Luis Antunes |
| 2006 | ISIT | Automatic Extraction of Meaning from the Web. | Rudi Cilibrasi, Paul M. B. Vitnyi |
| 2006 | ISIT | On Algorithmic Rate-Distortion Function. | Nikolai K. Vereshchagin, Paul M. B. Vitnyi |
| 2006 | OPODIS | About the Lifespan of Peer to Peer Networks, . | Rudi Cilibrasi, Zvi Lotker, Alfredo Navarra, Stephane Perennes, Paul M. B. Vitnyi |
| 2006 | TAMC | Similarity of Objects and the Meaning of Words. | Rudi Cilibrasi, Paul M. B. Vitnyi |
| 2005 | ITW | Universal similarity. | Paul M. B. Vitnyi |
| 2004 | STACS | Individual Communication Complexity: Extended Abstract. | Harry Buhrman, Hartmut Klauck, Nikolai K. Vereshchagin, Paul M. B. Vitnyi |
| 2003 | SODA | The similarity metric. | Ming Li, Xin Chen, Xin Li, Bin Ma, Paul M. B. Vitnyi |
| 2002 | COCOON | Sharpening Occam's Razor. | Ming Li, John Tromp, Paul M. B. Vitnyi |
| 2002 | FOCS | Kolmogorov's Structure Functions with an Application to the Foundations of Model Selection. | Nikolai K. Vereshchagin, Paul M. B. Vitnyi |
| 2002 | ISAAC | Meaningful Information. | Paul M. B. Vitnyi |
| 2002 | SIROCCO | A Protocol for Randomized Anonymous Two-process Wait-free Test-and-Set with Finite-state Verification. | John Tromp, Paul M. B. Vitnyi |
| 2001 | ICALP | Time and Space Bounds for Reversible Simulation. | Harry Buhrman, John Tromp, Paul M. B. Vitnyi |
| 2000 | ALT | Towards an Algorithmic Statistics. | Pter Gcs, John Tromp, Paul M. B. Vitnyi |
| 2000 | SOFSEM | The Incompressibility Method. | Tao Jiang, Ming Li, Paul M. B. Vitnyi |
| 1999 | ICALP | New Applications of the Incompressibility Method. | Harry Buhrman, Tao Jiang, Ming Li, Paul M. B. Vitnyi |
| 1999 | ICALP | Average-Case Complexity of Shellsort. | Tao Jiang, Ming Li, Paul M. B. Vitnyi |
| 1998 | SODA | Mutual Search (Extended Abstract). | Harry Buhrman, Matthew K. Franklin, Juan A. Garay, Jaap-Henk Hoepman, John Tromp, Paul M. B. Vitnyi |
| 1997 | COCOON | Mutual Search (abstract). | Paul M. B. Vitnyi |
| 1997 | FCT | Average-Case Analysis via Incompressibility. | Ming Li, Paul M. B. Vitnyi |
| 1996 | ALT | Genetic Fitness Optimization Using Rapidly Mixing Markov Chains. | Paul M. B. Vitnyi |
| 1996 | PODC | Optimal Routing Tables. | Harry Buhrman, Jaap-Henk Hoepman, Paul M. B. Vitnyi |
| 1995 | MFCS | Physics and the New Computation. | Paul M. B. Vitnyi |
| 1995 | WADS | Algorithmic Arguments in Physics of Computation. | Paul M. B. Vitnyi, Ming Li |
| 1994 | ESANN | Model selection for neural networks: comparing MDL and NIC. | Guido M. te Brake, Joost N. Kok, Paul M. B. Vitnyi |
| 1994 | ISAAC | Randomized Wait-Free Naming. | Alessandro Panconesi, Marina Papatriantafilou, Philippas Tsigas, Paul M. B. Vitnyi |
| 1994 | STOC | Two heads are better than two tapes. | Tao Jiang, Joel I. Seiferas, Paul M. B. Vitnyi |
| 1993 | STOC | Thermodynamics of computation and information distance. | Charles H. Bennett, Pter Gcs, Ming Li, Paul M. B. Vitnyi, Wojciech H. Zurek |
| 1992 | ICALP | Philosophical Issues in Kolmogorov Complexity. | Ming Li, Paul M. B. Vitnyi |
| 1989 | FOCS | A Theory of Learning Simple Concepts Under Simple Distributions and Average Case Complexity for the Universal Distribution (Extended Abstract) | Ming Li, Paul M. B. Vitnyi |
| 1989 | ICALP | How to Share Concurrent Asynchronous Wait-Free Varaibles (Preliminary Version). | Ming Li, Paul M. B. Vitnyi |
| 1989 | ICALP | A New Approach to Formal Language Theory by Kolmogorov Complexity (Preliminary Version). | Ming Li, Paul M. B. Vitnyi |
| 1987 | FOCS | Errata to "Atomic Shared Register Access by Asynchronous Hardware" | Paul M. B. Vitnyi, Baruch Awerbuch |
| 1986 | FOCS | Atomic Shared Register Access by Asynchronous Hardware (Detailed Abstract) | Paul M. B. Vitnyi, Baruch Awerbuch |
| 1985 | FOCS | Area Penalty for Sublinear Signal Propagation Delay on Chip (Preliminary Version) | Paul M. B. Vitnyi |
| 1985 | PODC | Distributed Match-Making for Processes in Computer Networks (Preliminary Version). | Sape J. Mullender, Paul M. B. Vitnyi |
| 1984 | ICALP | The Simple Roots of Real-Time Computation Hierarchies (Preliminary Version). | Paul M. B. Vitnyi |
| 1984 | STOC | Distributed Elections in an Archimedean Ring of Processors (Preliminary Version) | Paul M. B. Vitnyi |
| 1983 | ICALP | On the Simulation of Many Storage Heads by a Single One (Extended Abstract). | Paul M. B. Vitnyi |
| 1982 | ICALP | Efficient Simulations of Multicounter Machines. | Paul M. B. Vitnyi |
| 1982 | STOC | Real-Time Simulation of Multicounters by Oblivious One-Tape Turing Machines | Paul M. B. Vitnyi |
| 1980 | ICALP | On the Power of Real-Time Machines Under Varying Specifications (Extended Abstract). | Paul M. B. Vitnyi |
| 1980 | MFCS | Relativized Obliviousness. | Paul M. B. Vitnyi |
| 1977 | ICALP | Linear Time Simulation of Multihead Turing Machines with Head-to-Head Jumps. | Walter J. Savitch, Paul M. B. Vitnyi |