Michael O. Rabin

:For the violinist, see Michael Rabin (violinist)

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Michael O. Rabin (born 1931 in Breslau, Germany, today in Poland) is a noted computer scientist and a recipient of the Turing Award, the most prestigious award in the field.

Related Topics:
1931 - Breslau - Germany - Poland - Computer scientist - Turing Award

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Rabin was born as the son of a rabbi in what was then known as Breslau (it became Wrocław, see Wroclaw, 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.

Related Topics:
Rabbi - Wroclaw - Poland - Second World War - Hebrew University of Jerusalem - 1953 - Ph.D. - Princeton University - 1956

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

The citation for the Turing Award, awarded in 1976 jointly to Rabin and Dana Scott for a paper written in 1959, states that the award was granted:

Related Topics:
1976 - Dana Scott - 1959

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

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.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Nondeterministic machines have become a key concept in computational complexity theory, particularly with the description of complexity classes P and NP, as the most well-known example.

Related Topics:
Computational complexity theory - Complexity classes P and NP

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

In 1975, Rabin also invented a randomized algorithm, the Miller-Rabin primality test, that could determine very quickly, but with a tiny probability of error, whether a number was a prime number. Fast primality testing is key in the successful implementation of most public-key cryptography.

Related Topics:
1975 - Miller-Rabin primality test - Prime number

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

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.

Related Topics:
1987 - Richard Karp - String search algorithm - Rabin-Karp string search algorithm

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

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.

Related Topics:
Thomas J. Watson Sr. - Harvard University

~ ~ ~ ~ ~ ~ ~ ~ ~ ~