World Library  
Flag as Inappropriate
Email this Article

Michael O. Rabin

Article Id: WHEBN0000298404
Reproduction Date:

Title: Michael O. Rabin  
Author: World Heritage Encyclopedia
Language: English
Subject: Dana Scott, List of Turing Award laureates by university affiliation, List of important publications in theoretical computer science, Saharon Shelah, Alonzo Church
Collection: 1931 Births, Columbia University Faculty, Dijkstra Prize Laureates, Foreign Members of the Royal Society, German Jews, Hebrew University of Jerusalem Alumni, Hebrew University of Jerusalem Faculty, Iacr Fellows, Israel Prize in Computer Sciences Recipients, Israeli Computer Scientists, Israeli Jews, Israeli Mathematicians, Jewish Inventors, Living People, Logicians, Members of the Israel Academy of Sciences and Humanities, Members of the United States National Academy of Sciences, Modern Cryptographers, Tarski Lecturers, Theoretical Computer Scientists, Turing Award Laureates
Publisher: World Heritage Encyclopedia

Michael O. Rabin

Michael Oser Rabin
Born (1931-09-01) September 1, 1931
Breslau, Germany
Nationality Israeli
Fields Computer Science
Institutions Harvard University
Hebrew University
Columbia University
Alma mater Hebrew University (M.S.)
Princeton University (Ph.D.)
Thesis Recursive Unsolvability of Group Theoretic Problems (1957)
Doctoral advisor Alonzo Church
Doctoral students Moshé Machover
Saharon Shelah
Dov Gabbay
Giuseppe Persiano
Known for Miller-Rabin primality test
Rabin cryptosystem
Oblivious transfer
Rabin-Karp string search algorithm
Nondeterministic finite automata
Randomized algorithms
Notable awards Turing Award (1976)
Paris Kanellakis Award (2003)
Israel Prize
Emet Prize
Harvey Prize
Dan David Prize
Dijkstra Prize

Michael Oser Rabin (Hebrew: מִיכָאֵל עוזר רַבִּין‎, born September 1, 1931), is an Israeli computer scientist and a recipient of the Turing Award.


  • Biography 1
  • Awards 2
  • See also 3
  • References 4
  • External links 5


Rabin was born in 1931 in Breslau, Germany (today Wrocław, in Poland), the son of a rabbi. In 1935, he emigrated with his family to Mandate Palestine. As a young boy, he was very interested in mathematics and his father sent him to the best high school in Haifa, where he studied under a significant practicing mathematician, Elisha Netanyahu, who was then a high school teacher.[1]

After high school, he was drafted into the army during the 1948 Arab–Israeli War. The mathematician Abraham Fraenkel, who was a professor of mathematics in Jerusalem, intervened with the army command, and Rabin was discharged to study at the university in 1949.[1]

He received an M.Sc. from Hebrew University of Jerusalem in 1953 and a Ph.D. from Princeton University in 1956.

In the late 1950s, he was invited for a summer to do research for IBM at the Lamb Estate in Westchester County, New York with other promising mathematicians and scientists. It was there that he and Dana Scott wrote the paper "Finite Automata and Their Decision Problems".[2] Soon, using nondeterministic automata, they were able to re-prove Kleene's result that finite state machines exactly accept regular languages.[1]

As to the origins of what was to become computational complexity theory, the next summer Rabin returned to the Lamb Estate. John McCarthy posed a puzzle to him about spies, guards, and password which Rabin studied and soon after he wrote an article, "Degree of Difficulty of Computing a Function and Hierarchy of Recursive Sets."[1][3]

Nondeterministic machines have become a key concept in computational complexity theory, particularly with the description of complexity classes P and NP.

Rabin then returned to Jerusalem, researching logic, and working on the foundations of what would later be known as computer science. He was an associate professor and the head of the Institute of Mathematics at the Hebrew University at 29 years old, and a full professor by 33. Rabin recalls, "There was absolutely no appreciation of the work on the issues of computing. Mathematicians did not recognize the emerging new field".[1]

In 1960, he was invited by Edward F. Moore to work at Bell Labs, where Rabin introduced probabilistic automata that employ coin tosses in order to decide which state transitions to take. He showed examples of regular languages that required a very large number of states, but for which you get an exponential reduction of the number of states if you go over to probabilistic automata.[1]

In 1969, Rabin proved that the second-order theory of n successors is decidable.[4] 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 finished his tenure as Rector of the Hebrew University of Jerusalem and went to the Massachusetts Institute of Technology in the USA as a visiting professor. Gary Miller was also there and had his polynomial time test for primality based on the extended Riemann hypothesis. While there, Rabin 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.[5][6] 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 1976 he was invited by Joseph Traub to meet at Carnegie Mellon University and presented the primality test. After he gave that lecture, Traub had said, "No, no, this is revolutionary, and it's going to become very important."[1]

In 1979, Rabin invented the Rabin cryptosystem, the first asymmetric cryptosystem whose security was proved equivalent to the intractability of integer factorization.[7]

In 1981, Rabin reinvented a weak variant of the technique of oblivious transfer invented by Wiesner under the name of multiplexing,[8] 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.[9]

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.

Rabin is a foreign member of the United States National Academy of Sciences, a member of the French Academy of Sciences and a foreign member of the Royal Society.

He was also the PhD advisor of Saharon Shelah, a researcher in mathematical logic.


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

For their joint paper "Finite Automata and Their Decision Problems," which introduced the idea of nondeterministic machines, which has proved to be an enormously valuable concept. Their (Scott & Rabin) [sic] classic paper has been a continuous source of inspiration for subsequent work in this field.[11]

In 1995, Rabin was awarded the Israel Prize, in computer sciences.[12]

In 2010, Rabin was awarded the Tel Aviv University Dan David Prize ("Future" category), jointly with Leonard Kleinrock and Gordon E. Moore, for Computers and Telecommunications.[13]

See also


  1. ^ a b c d e f g Shasha, Dennis, "An Interview with Michael O. Rabin", Communications of the ACM, Vol. 53 No. 2, Pages 37-42, February 2010.
  2. ^  
  3. ^ Rabin, M.O., "Degree of Difficulty of Computing a Function and Hierarchy of Recursive Sets", Technical Report No. 2, O.N.R., Hebrew University, Jerusalem, 1960
  4. ^ Rabin, MO (1969). "Decidability of second order theories and automata on infinite trees". Trans. AMS 141: 1–35.  
  5. ^ Rabin, MO (1976). "Probabilistic algorithms". Algorithms and Complexity, Proc. Symp. Pittsburgh. 
  6. ^ Rabin, MO (1980). "Probabilistic algorithm for testing primality". Journal of Number Theory 12 (1): 128–138.  
  7. ^ Rabin, MO (January 1979). "Digitalized signatures and public-key functions as intractable as factorization" (PDF). MIT Laboratory of Computer Science Technical Report. Retrieved 2007-03-15. 
  8. ^ Rabin, Michael O. (1981). How to exchange secrets by oblivious transfer (Technical Report TR-81) (PDF). Aiken Computation Laboratory: Harvard University. 
  9. ^ Karp, RM; Rabin, MO (March 1987). "Efficient randomized pattern-matching algorithms". IBM Journal of Research and Development 31 (2): 249–260.  
  10. ^ Rabin, MO; Scott, D (April 1959). "Finite Automata and Their Decision Problems" (PDF, IEEE Xplore access required). IBM Journal of Research and Development 3 (2): 114–125.  
  11. ^ ACM Turing Award Citation
  12. ^ "Israel Prize Official Site - Recipients in 1995 (in Hebrew)". 
  13. ^ "Dan David Prize Official Site - Laureates 2010". 

External links

  • Short Description in an Information Science Hall of Fame at University of Pittsburgh
  • Oblivious transfer
  • Quotes from some of Professor Rabin's classes
  • Website for one of Rabin's courses
  • Description of Rabin's research by Richard J. Lipton
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.

Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.