John Tromp
Research Subjects
John Tromp has a total of 44 co-authors. Here are the top co-authors by number of shared publications:
Ming Li
4 shared publications- Paul Vitanyi
CWI University of Amsterdam
4 shared publications - Xin He
The State University of New York
4 shared publications - Bhaskar DasGupta
University of Illinois
3 shared publications - Harry Buhrman
CWI and University of Amsterdam
3 shared publications - Louxin Zhang
Department of Mathematics and Centre for Data Science and Machine Learning, National University of Singapore, Singapore 119076, Singapore
3 shared publications
Latest Publications
- Open Access
The Largest Number Representable in 64 Bits
We investigate how large an output can be computed by programs fitting inside a single register, using languages not designed for generating large outputs. We propose lambda calculus-based Busy Beaver functions that offer various advantages over the existing Turing machine-based ones, including a direct relation to Kolmogorov complexity.
Open AccessThe Largest Number Representable in 64 Bits
We investigate how large an output can be computed by programs fitting inside a single register, using languages not designed for generating large outputs. We propose lambda calculus-based Busy Beaver functions that offer various advantages over the existing Turing machine-based ones, including a direct relation to Kolmogorov complexity.
- Open Access
- 24 March 2026
- Published by MDPI AG in Preprints.org
The Largest Number Representable in 64 Bits
We investigate how large an output can be computed by programs fitting inside a single register.
- 24 March 2026
- Published by MDPI AG in Preprints.org
Open AccessThe Largest Number Representable in 64 Bits
We investigate how large an output can be computed by programs fitting inside a single register.
- 25 August 2014
- Published by Springer Nature
- p. 1-5
Nearest Neighbor Interchange and Related Distances
- 3 August 2007
- Published by Springer Nature in Algorithmica
- Vol. 49 (1) , 13-36
The Complexity of the Single Individual SNP Haplotyping Problem
- 3 August 2007
- Published by Springer Nature in Algorithmica
- Vol. 49 (1) , 13-36
The Complexity of the Single Individual SNP Haplotyping Problem
- Open Access
Prefix reversals on binary and ternary strings
Given a permutation pi, the application of prefix reversal f^(i) to pi reverses the order of the first i elements of pi. The problem of Sorting By Prefix Reversals (also known as pancake flipping), made famous by Gates and Papadimitriou (Bounds for sorting by prefix reversal, Discrete Mathematics 27, pp. 47-57), asks for the minimum number of prefix reversals required to sort the elements of a given permutation. In this paper we study a variant of this problem where the prefix reversals act not on permutations but on strings over a fixed size alphabet. We determine the minimum number of prefix reversals required to sort binary and ternary strings, with polynomial-time algorithms for these sorting problems as a result; demonstrate that computing the minimum prefix reversal distance between two binary strings is NP-hard; give an exact expression for the prefix reversal diameter of binary strings, and give bounds on the prefix reversal diameter of ternary strings. We also consider a weaker form of sorting called grouping (of identical symbols) and give polynomial-time algorithms for optimally grouping binary and ternary strings. A number of intriguing open problems are also discussed.
Open AccessPrefix reversals on binary and ternary strings
Given a permutation pi, the application of prefix reversal f^(i) to pi reverses the order of the first i elements of pi. The problem of Sorting By Prefix Reversals (also known as pancake flipping), made famous by Gates and Papadimitriou (Bounds for sorting by prefix reversal, Discrete Mathematics 27, pp. 47-57), asks for the minimum number of prefix reversals required to sort the elements of a given permutation. In this paper we study a variant of this problem where the prefix reversals act not on permutations but on strings over a fixed size alphabet. We determine the minimum number of prefix reversals required to sort binary and ternary strings, with polynomial-time algorithms for these sorting problems as a result; demonstrate that computing the minimum prefix reversal distance between two binary strings is NP-hard; give an exact expression for the prefix reversal diameter of binary strings, and give bounds on the prefix reversal diameter of ternary strings. We also consider a weaker form of sorting called grouping (of identical symbols) and give polynomial-time algorithms for optimally grouping binary and ternary strings. A number of intriguing open problems are also discussed.
- 1 April 2004
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 138 (3) , 253-263
On spaced seeds for similarity search
- 1 April 2004
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 138 (3) , 253-263
On spaced seeds for similarity search
- 1 March 2003
- Published by Elsevier in Information Processing Letters
- Vol. 85 (5) , 267-274
Sharpening Occam's razor
- 1 March 2003
- Published by Elsevier in Information Processing Letters
- Vol. 85 (5) , 267-274
Sharpening Occam's razor
- 1 July 2002
- Published by Springer Nature in Distributed Computing
- Vol. 15 (3) , 127-135
Randomized two-process wait-free test-and-set
- 1 July 2002
- Published by Springer Nature in Distributed Computing
- Vol. 15 (3) , 127-135
Randomized two-process wait-free test-and-set