| 2015 | FC | Cuckoo Cycle: A Memory Bound Graph-Theoretic Proof-of-Work. | John Tromp |
| 2005 | WABI | On the Complexity of Several Haplotyping Problems. | Rudi Cilibrasi, Leo van Iersel, Steven Kelk, John Tromp |
| 2003 | IJCAI | A Fast and Simple Algorithm for Bounds Consistency of the AllDifferent Constraint. | Alejandro Lpez-Ortiz, Claude-Guy Quimper, John Tromp, Peter van Beek |
| 2002 | COCOON | Sharpening Occam's Razor. | Ming Li, John Tromp, 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 |
| 1998 | SODA | Mutual Search (Extended Abstract). | Harry Buhrman, Matthew K. Franklin, Juan A. Garay, Jaap-Henk Hoepman, John Tromp, Paul M. B. Vitnyi |
| 1997 | SODA | On Distances between Phylogenetic Trees (Extended Abstract). | Bhaskar DasGupta, Xin He, Tao Jiang, Ming Li, John Tromp, Louxin Zhang |
| 1996 | COCOON | Some Notes on the Nearest Neighbour Interchange Distance. | Ming Li, John Tromp, Louxin Zhang |
| 1995 | ALT | Inferring a DNA Sequence from Erroneous Copies (Abstract). | John D. Kececioglu, Ming Li, John Tromp |
| 1995 | COCOON | Small Weight Bases for Hamming Codes. | John Tromp, Louxin Zhang, Ying Zhao |
| 1995 | STACS | Lower Bounds on Learning Decision Lists and Trees (Extended Abstract). | Thomas R. Hancock, Tao Jiang, Ming Li, John Tromp |
| 1991 | STOC | Linear Approximation of Shortest Superstrings | Avrim Blum, Tao Jiang, Ming Li, John Tromp, Mihalis Yannakakis |