Vviewpoints
DOI: 10.1145/1646353.1646369
Interview
An Interview with
ARt in
DeVeLoPment
Michael rabin
Michael O. Rabin, co-recipient of the 1976 ACM A.M. Turing Award,
discusses his innovative algorithmic work with Dennis Shasha.
Photogra Ph coUrt ESy oF Micha EL rabiN
IFIrST EnCOUnTErED Michael Rabin in 1980 when I was a first-year Ph.D. student at Har- vard University.Itwasfouryears after Rabin and Dana Scott
won the ACM A.M. Turing award for
their foundational work on determin-
istic and nondeterministic finite state
automata. By 1980, however, Rabin’s
interests were all about randomized
algorithms. His algorithms course was
a challenge to all of us. Sometimes he
presented a result he had worked out
only two weeks earlier. When I had dif-
ficulty understanding, I would make
puzzles for myself. As a consequence,
when I published my first puzzle book
The Puzzling Adventures of Dr. Ecco, I
dedicated the book to Michael as one
of my three most influential teachers.
At Harvard, I enjoyed every encounter
with Michael—in seminars and at par-
ties. He was a great raconteur and a
great joker. In 1994, journalist Cathy
Lazere and I embarked on the writ-
ing of Out of Their Minds: The Lives and
Discoveries of 15 Great Computer Scien-
tists. The goal was to interview great
living seminal thinkers of our field:
Knuth, Rabin, Dijkstra, among others.
Each thinker was associated with an
epithet: Michael’s was “the possibili-
ties of chance.”
—Dennis Shasha,
Shasha: I’m going to try to get to a
mixture of personal and technical
recollections, let’s start in Israel. You
finished high school, and what were
you thinking about doing after high
school?
