The Full Wiki

Michael O. Rabin: Map


Wikipedia article:

Map showing all locations mentioned on Wikipedia article:

For the violinist, see Michael Rabin .
Michael Oser Rabin ( , born September 1, 1931 in Breslaumarker, Germanymarker, today in Polandmarker) is a computer scientist and a recipient of the Turing Award.


Rabin was born as the son of a rabbi in what was then known as Breslau (it became Wrocław, and part of Polandmarker, after the Second World War). He received an M.Sc. from Hebrew University of Jerusalemmarker in 1953 and a Ph.D. from Princeton Universitymarker 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 Universitymarker and Professor of Computer Science at Hebrew Universitymarker. 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.


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.


  1. ACM Turing Award Citation

See also

External links

Embed code:

Got something to say? Make a comment.
Your name
Your email address