Michael O. Rabin
Michael Rabin (born 1931) is a noted computer scientist and a recipient of the Turing Award, the most prestigious award in the field.
Rabin was born in what was then known as Breslau, Germany (it became Wroclav, and part of Poland, after the Second World War). His father was a rabbi. He received an M. Sc. from Hebrew University in 1953, and a PhD from Princeton University in 1956.
The citation, awarded jointly to Rabin and Dana Scott, 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.
The paper was written in 1959.
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.
In 1975, Rabin also invented a randomized algorithm 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.
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.
Sources and External links
- http://www.sis.pitt.edu/~mbsclass/hall_of_fame/rabin.htm
- http://www.acm.org/awards/turing_citations/rabin.html
Referenced By
ACM Turing Award | List of computer scientists | List of mathematical topics (P-R) | Rabin | Turing Award
|
