John Tromp

Publication Activity (10 Years)

Years Active: 1989-2016
Publications (10 Years): 2

Top Topics

Cooperative Game

Hamiltonian Path

Top Venues

Computers and Games

Financial Cryptography Workshops

IACR Cryptol. ePrint Arch.

Publications

John Tromp
The Number of Legal Go Positions. Computers and Games (2016)
Matthieu Walraet, John Tromp
A Googolplex of Go Games. Computers and Games (2016)
John Tromp
Cuckoo Cycle: A Memory Bound Graph-Theoretic Proof-of-Work. Financial Cryptography Workshops (2015)
John Tromp
Cuckoo Cycle: a memory-hard proof-of-work system. IACR Cryptol. ePrint Arch. 2014 (2014)
Rudi Cilibrasi, Leo van Iersel, Steven Kelk, John Tromp
The Complexity of the Single Individual SNP Haplotyping Problem. Algorithmica 49 (1) (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)
Jing Zhang, Bo Jiang, Ming Li, John Tromp, Xuegong Zhang, Michael Q. Zhang
-values for DNA motifs. Bioinform. 23 (5) (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. Discret. Math. 21 (3) (2007)
John Tromp
Binary Lambda Calculus and Combinatory Logic. Kolmogorov Complexity and Applications (2006)
John Tromp, Gunnar Farnebäck
Combinatorics of Go. Computers and Games (2006)
John Tromp, Rudi Cilibrasi
Limits of Rush Hour Logic Complexity CoRR (2005)
Rudi Cilibrasi, Leo van Iersel, Steven Kelk, John Tromp
On the Complexity of Several Haplotyping Problems. WABI (2005)
Ming Li, Bin Ma, Derek Kisman, John Tromp
Patternhunter Ii: Highly Sensitive and Fast Homology Search. J. Bioinform. Comput. Biol. 2 (3) (2004)
Uri Keich, Ming Li, Bin Ma, John Tromp
On spaced seeds for similarity search. Discret. Appl. Math. 138 (3) (2004)
Ming Li, John Tromp, Paul M. B. Vitányi
Sharpening Occam's razor. Inf. Process. Lett. 85 (5) (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)
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)
Ming Li, John Tromp, Paul M. B. Vitányi
Sharpening Occam's Razor CoRR (2002)
Bin Ma, John Tromp, Ming Li
PatternHunter: faster and more sensitive homology search. Bioinform. 18 (3) (2002)
Xin Chen, Ming Li, Bin Ma, John Tromp
DNACompress: fast and effective DNA sequence compression. Bioinform. 18 (12) (2002)
Ming Li, John Tromp, Paul M. B. Vitányi
Sharpening Occam's Razor. COCOON (2002)
Péter Gács, John Tromp, Paul M. B. Vitányi
Correction to "Algorithmic statistics". IEEE Trans. Inf. Theory 48 (8) (2002)
John Tromp, Paul M. B. Vitányi
Randomized two-process wait-free test-and-set. Distributed Comput. 15 (3) (2002)
Harry Buhrman, John Tromp, Paul M. B. Vitányi
Time and Space Bounds for Reversible Simulation. ICALP (2001)
Harry Buhrman, John Tromp, Paul M. B. Vitányi
Time and Space Bounds for Reversible Simulation CoRR (2001)
John Tromp, Paul M. B. Vitányi
Randomized Two-Process Wait-Free Test-and-Set CoRR (2001)
Kazuyuki Amano, John Tromp, Paul M. B. Vitányi, Osamu Watanabe
On a Generalized Ruin Problem. RANDOM-APPROX (2001)
Péter Gács, John Tromp, Paul M. B. Vitányi
Algorithmic statistics. IEEE Trans. Inf. Theory 47 (6) (2001)
Frédéric Gruau, John Tromp
Cellular Gravity. Parallel Process. Lett. 10 (4) (2000)
Péter Gács, John Tromp, Paul M. B. Vitányi
Algorithmic Statistics CoRR (2000)
Péter Gács, John Tromp, Paul M. B. Vitányi
Towards an Algorithmic Statistics. ALT (2000)
Marcel Crâsmaru, John Tromp
Ladders Are PSPACE-Complete. Computers and Games (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) (1999)
Harry Buhrman, Ming Li, John Tromp, Paul M. B. Vitányi
Kolmogorov Random Graphs and the Incompressibility Method. SIAM J. Comput. 29 (2) (1999)
Harry Buhrman, Matthew K. Franklin, Juan A. Garay, Jaap-Henk Hoepman, John Tromp, Paul M. B. Vitányi
Mutual Search CoRR (1999)
Bhaskar DasGupta, Xin He, Tao Jiang, Ming Li, John Tromp, Louxin Zhang
On computing the nearest neighbor interchange distance. Discrete Mathematical Problems with Medical Applications (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) (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)
Ming Li, John Tromp, Paul M. B. Vitányi
Reversible Simulation of Irreversible Computation by Pebble Games CoRR (1997)
John D. Kececioglu, Ming Li, John Tromp
Inferring a DNA Sequence from Erroneous Copies. Theor. Comput. Sci. 185 (1) (1997)
John Tromp, Louxin Zhang, Ying Zhao
Small Weight Bases for Hamming Codes. Theor. Comput. Sci. 181 (2) (1997)
Bhaskar DasGupta, Xin He, Tao Jiang, Ming Li, John Tromp, Louxin Zhang
On Distances between Phylogenetic Trees (Extended Abstract). SODA (1997)
Ming Li, John Tromp, Louxin Zhang
Some Notes on the Nearest Neighbour Interchange Distance. COCOON (1996)
Ming Li, John Tromp, Paul M. B. Vitányi
How to Share Concurrent Wait-Free Variables. J. ACM 43 (4) (1996)
Siegfried Lehr, Jeffrey O. Shallit, John Tromp
On the Vector Space of the Automatic Reals. Theor. Comput. Sci. 163 (1&2) (1996)
Thomas R. Hancock, Tao Jiang, Ming Li, John Tromp
Lower Bounds on Learning Decision Lists and Trees. Inf. Comput. 126 (2) (1996)
John Tromp, Jeffrey O. Shallit
Subword Complexity of a Generalized Thue-Morse Word. Inf. Process. Lett. 54 (6) (1995)
John Tromp, Louxin Zhang, Ying Zhao
Small Weight Bases for Hamming Codes. COCOON (1995)
John D. Kececioglu, Ming Li, John Tromp
Inferring a DNA Sequence from Erroneous Copies (Abstract). ALT (1995)
Thomas R. Hancock, Tao Jiang, Ming Li, John Tromp
Lower Bounds on Learning Decision Lists and Trees (Extended Abstract). STACS (1995)
Avrim Blum, Tao Jiang, Ming Li, John Tromp, Mihalis Yannakakis
Linear Approximation of Shortest Superstrings. J. ACM 41 (4) (1994)
John Tromp
On Update-Last Schemes. Parallel Process. Lett. 3 (1993)
Jaap-Henk Hoepman, John Tromp
Binary Snapshots. WDAG (1993)
John Tromp, Peter van Emde Boas
Associative Storage Modification Machines. Complexity Theory: Current Research (1992)
Yehuda Afek, Eli Gafni, John Tromp, Paul M. B. Vitányi
Wait-free Test-and-Set (Extended Abstract). WDAG (1992)
Avrim Blum, Tao Jiang, Ming Li, John Tromp, Mihalis Yannakakis
Linear Approximation of Shortest Superstrings STOC (1991)
John Tromp
How to Construct an Atomic Variable (Extended Abstract). WDAG (1989)