John Tromp

2008
53	EE	Bhaskar DasGupta, Xin He, Tao Jiang, Ming Li, John Tromp, Louxin Zhang: Nearest Neighbor Interchange and Related Distances. Encyclopedia of Algorithms 2008
2007
52	EE	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
51	EE	Rudi Cilibrasi, Leo van Iersel, Steven Kelk, John Tromp: The Complexity of the Single Individual SNP Haplotyping Problem. Algorithmica 49(1): 13-36 (2007)
50	EE	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)
49	EE	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)
2006
48	EE	John Tromp, Gunnar Farnebäck: Combinatorics of Go. Computers and Games 2006: 84-99
47	EE	John Tromp: Binary Lambda Calculus and Combinatory Logic. Kolmogorov Complexity and Applications 2006
2005
46	EE	Rudi Cilibrasi, Leo van Iersel, Steven Kelk, John Tromp: On the Complexity of Several Haplotyping Problems. WABI 2005: 128-139
45	EE	John Tromp, Rudi Cilibrasi: Limits of Rush Hour Logic Complexity CoRR abs/cs/0502068: (2005)
2004
44	EE	Uri Keich, Ming Li, Bin Ma, John Tromp: On spaced seeds for similarity search. Discrete Applied Mathematics 138(3): 253-263 (2004)
43	EE	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)
2003
42		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
41	EE	Ming Li, John Tromp, Paul M. B. Vitányi: Sharpening Occam's razor. Inf. Process. Lett. 85(5): 267-274 (2003)
2002
40	EE	Ming Li, John Tromp, Paul M. B. Vitányi: Sharpening Occam's Razor. COCOON 2002: 411-419
39		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
38		Xin Chen, Ming Li, Bin Ma, John Tromp: DNACompress: fast and effective DNA sequence compression. Bioinformatics 18(12): 1696-1698 (2002)
37		Bin Ma, John Tromp, Ming Li: PatternHunter: faster and more sensitive homology search. Bioinformatics 18(3): 440-445 (2002)
36	EE	Ming Li, John Tromp, Paul M. B. Vitányi: Sharpening Occam's Razor CoRR cs.LG/0201005: (2002)
35	EE	John Tromp, Paul M. B. Vitányi: Randomized two-process wait-free test-and-set. Distributed Computing 15(3): 127-135 (2002)
34		Péter Gács, John Tromp, Paul M. B. Vitányi: Correction to "Algorithmic statistics". IEEE Transactions on Information Theory 48(8): 2427 (2002)
2001
33	EE	Harry Buhrman, John Tromp, Paul M. B. Vitányi: Time and Space Bounds for Reversible Simulation. ICALP 2001: 1017-1027
32	EE	Kazuyuki Amano, John Tromp, Paul M. B. Vitányi, Osamu Watanabe: On a Generalized Ruin Problem. RANDOM-APPROX 2001: 181-191
31	EE	John Tromp, Paul M. B. Vitányi: Randomized Two-Process Wait-Free Test-and-Set CoRR cs.DC/0106056: (2001)
30	EE	Harry Buhrman, John Tromp, Paul M. B. Vitányi: Time and Space Bounds for Reversible Simulation CoRR quant-ph/0101133: (2001)
29		Péter Gács, John Tromp, Paul M. B. Vitányi: Algorithmic statistics. IEEE Transactions on Information Theory 47(6): 2443-2463 (2001)
2000
28	EE	Péter Gács, John Tromp, Paul M. B. Vitányi: Towards an Algorithmic Statistics. ALT 2000: 41-55
27	EE	Marcel Crâsmaru, John Tromp: Ladders Are PSPACE-Complete. Computers and Games 2000: 241-249
26	EE	Péter Gács, John Tromp, Paul M. B. Vitányi: Algorithmic Statistics CoRR math.PR/0006233: (2000)
25		Frédéric Gruau, John Tromp: Cellular Gravity. Parallel Processing Letters 10(4): 383-393 (2000)
1999
24	EE	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)
23	EE	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)
22	EE	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)
21		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)
1998
20		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
1997
19		Bhaskar DasGupta, Xin He, Tao Jiang, Ming Li, John Tromp, Louxin Zhang: On Distances between Phylogenetic Trees (Extended Abstract). SODA 1997: 427-436
18	EE	Ming Li, John Tromp, Paul M. B. Vitányi: Reversible Simulation of Irreversible Computation by Pebble Games CoRR quant-ph/9703009: (1997)
17	EE	John Tromp, Louxin Zhang, Ying Zhao: Small Weight Bases for Hamming Codes. Theor. Comput. Sci. 181(2): 337-345 (1997)
16	EE	John D. Kececioglu, Ming Li, John Tromp: Inferring a DNA Sequence from Erroneous Copies. Theor. Comput. Sci. 185(1): 3-13 (1997)
1996
15		Ming Li, John Tromp, Louxin Zhang: Some Notes on the Nearest Neighbour Interchange Distance. COCOON 1996: 343-351
14		Thomas R. Hancock, Tao Jiang, Ming Li, John Tromp: Lower Bounds on Learning Decision Lists and Trees. Inf. Comput. 126(2): 114-122 (1996)
13	EE	Ming Li, John Tromp, Paul M. B. Vitányi: How to Share Concurrent Wait-Free Variables. J. ACM 43(4): 723-746 (1996)
12	EE	Siegfried Lehr, Jeffrey Shallit, John Tromp: On the Vector Space of the Automatic Reals. Theor. Comput. Sci. 163(1&2): 193-210 (1996)
1995
11		John D. Kececioglu, Ming Li, John Tromp: Inferring a DNA Sequence from Erroneous Copies (Abstract). ALT 1995: 151-152
10		John Tromp, Louxin Zhang, Ying Zhao: Small Weight Bases for Hamming Codes. COCOON 1995: 235-243
9		Thomas R. Hancock, Tao Jiang, Ming Li, John Tromp: Lower Bounds on Learning Decision Lists and Trees (Extended Abstract). STACS 1995: 527-538
8	EE	John Tromp, Jeffrey Shallit: Subword Complexity of a Generalized Thue-Morse Word. Inf. Process. Lett. 54(6): 313-316 (1995)
1994
7	EE	Avrim Blum, Ming Li, John Tromp, Mihalis Yannakakis: Linear Approximation of Shortest Superstrings. J. ACM 41(4): 630-647 (1994)
1993
6		Jaap-Henk Hoepman, John Tromp: Binary Snapshots. WDAG 1993: 18-25
5		John Tromp: On Update-Last Schemes. Parallel Processing Letters 3: 25-28 (1993)
1992
4		John Tromp, Peter van Emde Boas: Associative Storage Modification Machines. Complexity Theory: Current Research 1992: 291-313
3		Yehuda Afek, Eli Gafni, John Tromp, Paul M. B. Vitányi: Wait-free Test-and-Set (Extended Abstract). WDAG 1992: 85-94
1991
2		Avrim Blum, Tao Jiang, Ming Li, John Tromp, Mihalis Yannakakis: Linear Approximation of Shortest Superstrings STOC 1991: 328-336
1989
1		John Tromp: How to Construct an Atomic Variable (Extended Abstract). WDAG 1989: 292-302

Coauthor Index

1	Yehuda Afek	[3]
2	Kazuyuki Amano	[32]
3	Peter van Beek	[42]
4	Avrim Blum	[2] [7]
5	Peter van Emde Boas	[4]
6	Harry Buhrman	[20] [21] [22] [23] [30] [33]
7	Xin Chen	[38]
8	Rudi Cilibrasi	[45] [46] [51]
9	Marcel Crâsmaru	[27]
10	Bhaskar DasGupta	[19] [24] [53]
11	Gunnar Farnebäck	[48]
12	Matthew K. Franklin	[20] [22] [23]
13	Péter Gács	[26] [28] [29] [34]
14	Eli Gafni	[3]
15	Juan A. Garay	[20] [22] [23]
16	Frédéric Gruau	[25]
17	Thomas R. Hancock	[9] [14]
18	Xin He	[19] [24] [53]
19	Jaap-Henk Hoepman	[6] [20] [22] [23]
20	Cor A. J. Hurkens	[49] [52]
21	Leo van Iersel	[46] [49] [51] [52]
22	Bo Jiang	[50]
23	Tao Jiang	[2] [9] [14] [19] [24] [53]
24	John D. Kececioglu	[11] [16]
25	Uri Keich	[44]
26	Judith Keijsper (J. C. M. Keijsper)	[49] [52]
27	Steven Kelk	[46] [49] [51] [52]
28	Derek Kisman	[43]
29	Siegfried Lehr	[12]
30	Ming Li	[2] [7] [9] [11] [13] [14] [15] [16] [18] [19] [21] [24] [36] [37] [38] [40] [41] [43] [44] [50] [53]
31	Alejandro López-Ortiz	[42]
32	Bin Ma	[37] [38] [43] [44]
33	Claude-Guy Quimper	[42]
34	Jeffrey Shallit	[8] [12]
35	Leen Stougie	[49] [52]
36	Paul M. B. Vitányi	[3] [13] [18] [20] [21] [22] [23] [26] [28] [29] [30] [31] [32] [33] [34] [35] [36] [39] [40] [41]
37	Osamu Watanabe	[32]
38	Mihalis Yannakakis	[2] [7]
39	Jing Zhang	[50]
40	Louxin Zhang	[10] [15] [17] [19] [53]
41	Michael Q. Zhang	[50]
42	Xuegong Zhang	[50]
43	Ying Zhao	[10] [17]

Colors in the list of coauthors