John Tromp

Bhaskar DasGupta, Xin He, Tao Jiang, Ming Li, John Tromp, Louxin Zhang: Nearest Neighbor Interchange and Related Distances. Encyclopedia of Algorithms 2008

Rudi Cilibrasi, Leo van Iersel, Steven Kelk, John Tromp: The Complexity of the Single Individual SNP Haplotyping Problem. Algorithmica 49(1): 13-36 (2007)

Jing Zhang, Bo Jiang, Ming Li, John Tromp, Xuegong Zhang, Michael Q. Zhang: Computing exact P-values for DNA motifs. Bioinformatics 23(5): 531-537 (2007)

Cor A. J. Hurkens, Leo van Iersel, Judith Keijsper, Steven Kelk, Leen Stougie, John Tromp: Prefix Reversals on Binary and Ternary Strings. SIAM J. Discrete Math. 21(3): 592-611 (2007)

Cor A. J. Hurkens, Leo van Iersel, Judith Keijsper, Steven Kelk, Leen Stougie, John Tromp: Prefix Reversals on Binary and Ternary Strings. AB 2007: 292-306

John Tromp, Gunnar Farnebäck: Combinatorics of Go. Computers and Games 2006: 84-99

John Tromp: Binary Lambda Calculus and Combinatory Logic. Kolmogorov Complexity and Applications 2006

Rudi Cilibrasi, Leo van Iersel, Steven Kelk, John Tromp: On the Complexity of Several Haplotyping Problems. WABI 2005: 128-139

John Tromp, Rudi Cilibrasi: Limits of Rush Hour Logic Complexity. CoRR abs/cs/0502068 (2005)

Uri Keich, Ming Li, Bin Ma, John Tromp: On spaced seeds for similarity search. Discrete Applied Mathematics 138(3): 253-263 (2004)

Ming Li, Bin Ma, Derek Kisman, John Tromp: Patternhunter Ii: Highly Sensitive and Fast Homology Search. J. Bioinformatics and Computational Biology 2(3): 417-440 (2004)

Ming Li, John Tromp, Paul M. B. Vitányi: Sharpening Occam's razor. Inf. Process. Lett. 85(5): 267-274 (2003)

Alejandro López-Ortiz, Claude-Guy Quimper, John Tromp, Peter van Beek: A Fast and Simple Algorithm for Bounds Consistency of the AllDifferent Constraint. IJCAI 2003: 245-250

Bin Ma, John Tromp, Ming Li: PatternHunter: faster and more sensitive homology search. Bioinformatics 18(3): 440-445 (2002)

Xin Chen, Ming Li, Bin Ma, John Tromp: DNACompress: fast and effective DNA sequence compression. Bioinformatics 18(12): 1696-1698 (2002)

John Tromp, Paul M. B. Vitányi: Randomized two-process wait-free test-and-set. Distributed Computing 15(3): 127-135 (2002)

Péter Gács, John Tromp, Paul M. B. Vitányi: Correction to "Algorithmic statistics". IEEE Transactions on Information Theory 48(8): 2427 (2002)

Ming Li, John Tromp, Paul M. B. Vitányi: Sharpening Occam's Razor. COCOON 2002: 411-419

John Tromp, Paul M. B. Vitányi: A Protocol for Randomized Anonymous Two-process Wait-free Test-and-Set with Finite-state Verification. SIROCCO 2002: 275-291

Ming Li, John Tromp, Paul M. B. Vitányi: Sharpening Occam's Razor. CoRR cs.LG/0201005 (2002)

Péter Gács, John Tromp, Paul M. B. Vitányi: Algorithmic statistics. IEEE Transactions on Information Theory 47(6): 2443-2463 (2001)

Harry Buhrman, John Tromp, Paul M. B. Vitányi: Time and Space Bounds for Reversible Simulation. ICALP 2001: 1017-1027

Kazuyuki Amano, John Tromp, Paul M. B. Vitányi, Osamu Watanabe: On a Generalized Ruin Problem. RANDOM-APPROX 2001: 181-191

John Tromp, Paul M. B. Vitányi: Randomized Two-Process Wait-Free Test-and-Set. CoRR cs.DC/0106056 (2001)

Harry Buhrman, John Tromp, Paul M. B. Vitányi: Time and Space Bounds for Reversible Simulation. CoRR quant-ph/0101133 (2001)

Frédéric Gruau, John Tromp: Cellular Gravity. Parallel Processing Letters 10(4): 383-393 (2000)

Péter Gács, John Tromp, Paul M. B. Vitányi: Towards an Algorithmic Statistics. ALT 2000: 41-55

Marcel Crâsmaru, John Tromp: Ladders Are PSPACE-Complete. Computers and Games 2000: 241-249

Péter Gács, John Tromp, Paul M. B. Vitányi: Algorithmic Statistics. CoRR math.PR/0006233 (2000)

Bhaskar DasGupta, Xin He, Tao Jiang, Ming Li, John Tromp: On the Linear-Cost Subtree-Transfer Distance between Phylogenetic Trees. Algorithmica 25(2-3): 176-195 (1999)

Harry Buhrman, Matthew K. Franklin, Juan A. Garay, Jaap-Henk Hoepman, John Tromp, Paul M. B. Vitányi: Mutual Search. J. ACM 46(4): 517-536 (1999)

Harry Buhrman, Ming Li, John Tromp, Paul M. B. Vitányi: Kolmogorov Random Graphs and the Incompressibility Method. SIAM J. Comput. 29(2): 590-599 (1999)

Harry Buhrman, Matthew K. Franklin, Juan A. Garay, Jaap-Henk Hoepman, John Tromp, Paul M. B. Vitányi: Mutual Search. CoRR cs.DS/9902005 (1999)

Harry Buhrman, Matthew K. Franklin, Juan A. Garay, Jaap-Henk Hoepman, John Tromp, Paul M. B. Vitányi: Mutual Search (Extended Abstract). SODA 1998: 481-489

John Tromp, Louxin Zhang, Ying Zhao: Small Weight Bases for Hamming Codes. Theor. Comput. Sci. 181(2): 337-345 (1997)

John D. Kececioglu, Ming Li, John Tromp: Inferring a DNA Sequence from Erroneous Copies. Theor. Comput. Sci. 185(1): 3-13 (1997)

Bhaskar DasGupta, Xin He, Tao Jiang, Ming Li, John Tromp, Louxin Zhang: On Distances between Phylogenetic Trees (Extended Abstract). SODA 1997: 427-436

Ming Li, John Tromp, Paul M. B. Vitányi: Reversible Simulation of Irreversible Computation by Pebble Games. CoRR quant-ph/9703009 (1997)

Thomas R. Hancock, Tao Jiang, Ming Li, John Tromp: Lower Bounds on Learning Decision Lists and Trees. Inf. Comput. 126(2): 114-122 (1996)

Ming Li, John Tromp, Paul M. B. Vitányi: How to Share Concurrent Wait-Free Variables. J. ACM 43(4): 723-746 (1996)

Siegfried Lehr, Jeffrey Shallit, John Tromp: On the Vector Space of the Automatic Reals. Theor. Comput. Sci. 163(1&2): 193-210 (1996)

Ming Li, John Tromp, Louxin Zhang: Some Notes on the Nearest Neighbour Interchange Distance. COCOON 1996: 343-351

John Tromp, Jeffrey Shallit: Subword Complexity of a Generalized Thue-Morse Word. Inf. Process. Lett. 54(6): 313-316 (1995)

John D. Kececioglu, Ming Li, John Tromp: Inferring a DNA Sequence from Erroneous Copies (Abstract). ALT 1995: 151-152

John Tromp, Louxin Zhang, Ying Zhao: Small Weight Bases for Hamming Codes. COCOON 1995: 235-243

Thomas R. Hancock, Tao Jiang, Ming Li, John Tromp: Lower Bounds on Learning Decision Lists and Trees (Extended Abstract). STACS 1995: 527-538

Avrim Blum, Tao Jiang, Ming Li, John Tromp, Mihalis Yannakakis: Linear Approximation of Shortest Superstrings. J. ACM 41(4): 630-647 (1994)

John Tromp: On Update-Last Schemes. Parallel Processing Letters 3: 25-28 (1993)

Jaap-Henk Hoepman, John Tromp: Binary Snapshots. WDAG 1993: 18-25

John Tromp, Peter van Emde Boas: Associative Storage Modification Machines. Complexity Theory: Current Research 1992: 291-313

Yehuda Afek, Eli Gafni, John Tromp, Paul M. B. Vitányi: Wait-free Test-and-Set (Extended Abstract). WDAG 1992: 85-94

Avrim Blum, Tao Jiang, Ming Li, John Tromp, Mihalis Yannakakis: Linear Approximation of Shortest Superstrings. STOC 1991: 328-336

John Tromp: How to Construct an Atomic Variable (Extended Abstract). WDAG 1989: 292-302