John Tromp

Research Interests

Board Games and Artificial Intelligence, Algorithms, Complexity, Algorithmic Information Theory, Distributed Computing, Computational biology, and what not. Recently i've constructed an efficient ranking of chess positions, which allows for accurate estimates of the number of legal positions. More recently, I've explored a new form of numerals in Combinatory Logic. Less recent research has focused on a new Proof-of-Work system called Cuckoo Cycle, and on the Combinatorics of Go, specifically counting the number of legal positions. I've been playing with a Lambda Calculus based utterly simple computer model. My Erdös number is 2, courtesy of Jeffrey Shallit, my favourite CS lecturer, who coauthored papers with both me and Erdös. A while ago I studied the complexity of OriMazes.

Recreational Interests

I guess I'm sort of addicted to the game of Go. Having learned the game at the age of 24, I've now reached the rank of 2 dan, hoping to one day make it to 3 dan. Chess used to be my favourite game, and I can still occasionally be tempted to play some blitz chess. A nice game of Risk can be quite enjoyable too, although it's a little difficult to find 2 or 3 playing partners.

When I was still a PhD student, under the supervision of Paul Vitányi, I thought of doing a thesis on the game of connect-4. Instead, I ended up working on distributed computing problems, and many other topics in my PhD research, which resulted in this thesis.

Since the early 90s, I've been fascinated by recumbent bikes. Check out this picture of a Green Machine, a design concept that in 2005 has finally been revived in a slightly different form. Since 2017, I am the proud owner of an M5 M-racer. replacing my Optima Condor from 2000.

Weather permitting, I love to go inline skating on my Rollerblade Tempest 110.

Here's a picture of the apartment building I moved into summer 2017.

I like to think of cute algorithms (or take other peoples') and write them in the absolute minimum amount of code, greatly obfuscating them in the process. See my programming pearls.

See my CD collection to get an idea of my taste in music.

If your browser can preview postscript, have a look at my signature:
```%!PS                            % -John Tromp http://tromp.github.io/
42 42 scale 7 9 translate .07 setlinewidth .5 setgray/c{arc clip fill
setgray}def 1 0 0 42 1 0 c 0 1 1{0 3 3 90 270 arc 0 0 6 0 -3 3 90 270
arcn 270 90 c -2 2 4{-6 moveto 0 12 rlineto}for -5 2 5{-3 exch moveto
9 0 rlineto}for stroke 0 0 3 1 1 0 c 180 rotate initclip}for showpage
```
(when using ghostview make sure to turn off Antialias under State/gv Options or the colors won't show correctly) or this one:
```%!PS                           % -John Tromp http://tromp.github.io/
/t{dup 1 sub gsave dup 0 gt{[.4 .2 -.2 .4 .4 .2]concat t currentgray
.8 mul .2 add setgray -1 1 scale t -1 2 translate t 1 -1 scale t[0 1
1 0 0 2]concat t pop}{0 moveto 1 0 lineto 0 2 lineto closepath clip
fill}ifelse grestore}def 10 10 translate 600 600 scale 5 t showpage
```