- For the violinist, see Michael Rabin .
Michael Oser Rabin ( , born
September 1, 1931 in Breslau, Germany, today in
Poland) is a computer
scientist and a recipient of the Turing
Award.
Biography
Rabin was
born as the son of a rabbi in what was then
known as Breslau (it became Wrocław, and part of Poland, after the
Second World War).
He
received an M.Sc. from Hebrew University of Jerusalem in 1953 and a Ph.D. from Princeton
University in 1956.
Nondeterministic machines
have become a key concept in
computational complexity
theory, particularly with the description of
complexity classes P and NP.
In 1969, Rabin proved that the
second-order theory of n successors is
decidable. A key component of the proof
implicitly showed
determinacy of
parity games, which lie in the third
level of the
Borel hierarchy.
In 1975, Rabin also invented the
Miller-Rabin primality test, a
randomized algorithm that can determine very quickly (but with a
tiny probability of error) whether a number is
prime. Rabin's method was based on previous
work of
Gary Miller that
solved the problem deterministically with the assumption that the
generalized Riemann
hypothesis is true, but Rabin's version of the test made no
such assumption. Fast primality testing is key in the successful
implementation of most public-key cryptography, and in 2003 Miller,
Rabin,
Robert M. Solovay, and
Volker Strassen were given the
Paris Kanellakis Award for their work
on primality testing.
In 1979, Rabin invented the
Rabin
cryptosystem, the first asymmetric cryptosystem whose security
was proved equivalent to the intractability of
integer factorization.
In 1981, Rabin reinvented a weak variant of the technique of
oblivious transfer invented by
Wiesner under the name of multiplexing , allowing a sender to
transmit a message to a receiver where the receiver has some
probability between 0 and 1 of learning the message, with the
sender being unaware whether the receiver was able to do so.
In 1987, Rabin, together with
Richard
Karp, created one of the most well-known efficient
string search algorithms, the
Rabin-Karp string
search algorithm, known for its rolling hash.
Rabin's more recent research has concentrated on computer security.
He is currently the
Thomas J.
Watson Sr. Professor of Computer Science at
Harvard
University and Professor of Computer Science at Hebrew
University.
During the spring semester of 2007, he was a visiting professor at
Columbia University teaching
Introduction to Cryptography.
He was also the PhD advisor of
Saharon
Shelah, one of the preeminent active researchers in
mathematical logic.
Awards
In 1976, the
Turing Award was awarded
jointly to Rabin and
Dana Scott for a
paper written in 1959, the citation for which states that the award
was granted:
For their joint paper "Finite Automata and Their
Decision Problem," which introduced the idea of nondeterministic
machines, which has proved to be an enormously valuable
concept. Their (Scott & Rabin) classic paper has been
a continuous source of inspiration for subsequent work in this
field.
In 1995, Rabin was awarded the
Israel
Prize, in computer sciences.
References
- ACM Turing Award Citation
See also
External links