John Tromp

John Tromp

Auto-generated profile, based on publicly available information

John Tromp

Centrum voor Wiskunde en Informatica (CWI) Kruislaan 413 1098 SJ Amsterdam Netherlands

Research Focus & Metrics

Academic Career Length

34Years (1993-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
1 July 1994 in Journal of the ACM
Verified
Journal Article
Open access
ABAvrim Blum
Avrim Blum
TJTao Jiang
Tao Jiang
MLMing Li
Ming Li
JTJohn Tromp
John Tromp
MYMihalis Yannakakis
Mihalis Yannakakis
We consider the following problem: given a collection of strings s 1 ,…, s m , find the shortest string s such that each s i appears as a substring (a consecutive block) of s . Although this problem is known to be NP-hard, a simple greedy procedure appears to do quite well and is routinely used in DNA sequencing and data compression practice, namely: repeatedly merge the pair of (distinct) strings with maximum overlap until only one string remains. Let n denote the length of the optimal superstring. A common conjecture states that the above greedy procedure produces a superstring of length O(n) (in fact, 2 n ), yet the only previous nontrivial bound known for any polynomial-time algorithm is a recent O(n log n ) result. We show that the greedy algorithm does in fact achieve a constant factor approximation, proving an upper bound of 4 n . Furthermore, we present a simple modified version of the greedy algorithm that we show produces a superstring of length at most 3 n . We also show the superstring problem to be MAXSNP-hard, which implies that a polynomial-time approximation scheme for this problem is unlikely.

1 April 2004 in Discrete Applied Mathematics
Verified
Journal Article
Closed access
UKUri Keich
Uri Keich
MLMing Li
Ming Li
BMBin Ma
Bin Ma
JTJohn Tromp
John Tromp

1 October 1996 in Journal of Theoretical Biology
Verified
Journal Article
Closed access
MLMing Li
Ming Li
JTJohn Tromp
John Tromp
LZLouxin Zhang
Louxin Zhang

3 August 2007 in Algorithmica
Verified
Journal Article
Closed access
PDF file
RCRudi Cilibrasi
Rudi Cilibrasi
LILeo van Iersel
Leo van Iersel
SKSteven Kelk
Steven Kelk
JTJohn Tromp
John Tromp

1 July 1996 in Journal of the ACM
Verified
Journal Article
Open access
MLMing Li
Ming Li
JTJohn Tromp
John Tromp
PVPaul M. B. Vitányi
Paul M. B. Vitányi
Sharing data between multiple asynchronous users—each of which can atomically read and write the data—is a feature that may help to increase the amount of parallelism in distributed systems. An algorithm implementing this feature is presented. The main construction of ann-user atomic variable directly from single-writer, single-reader atomic variables usesO(n)control bits andO(n)accesses per Read/Write running inO(1)parallel time.

24 August 2001 in Journal of Physics A: General Physics
Verified
Journal Article
Closed access
PDF file
HBHarry Buhrman
Harry Buhrman
JTJohn Tromp
John Tromp
PVPaul Vitányi
Paul Vitányi
We prove a general upper bound on the trade-off between time and space that suffices for the reversible simulation of irreversible computation. Previously, only simulations using exponential time or quadratic space were known. The trade-off shows for the first time that we can simultaneously achieve subexponential time and subquadratic space. The boundary values are the exponential time with hardly any extra space required by the Lange–McKenzie–Tapp method and the (log 3)th power time with square space required by the Bennett method. We also give the first general lower bound on the extra storage space required by general reversible simulation. This lower bound is optimal in that it is achieved by some reversible simulations.