Michael O. Rabin

Source: Wikipedia, the free encyclopedia.
Michael Oser Rabin
Awards
Scientific career
FieldsComputer science
InstitutionsHarvard University
Hebrew University of Jerusalem
Columbia University
ThesisRecursive Unsolvability of Group Theoretic Problems (1957)
Doctoral advisorAlonzo Church
Doctoral students

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

Biography

Early life and education

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 mathematician Elisha Netanyahu, who was then a high school teacher.[1]

Rabin graduated from the Hebrew Reali School in Haifa in 1948, and 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] Afterwards, he received an M.Sc from Hebrew University of Jerusalem. He began graduate studies at the University of Pennsylvania before receiving a Ph.D. from Princeton University in 1956.[2]

Career

Rabin became Associate Professor of Mathematics at the

MIT (1962-63). Before moving to Harvard University as Gordon McKay Professor of Computer Science in 1981, he was a professor at the Hebrew University.[3]

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".[4] 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 passwords, which Rabin studied and soon after he wrote an article, "Degree of Difficulty of Computing a Function and Hierarchy of Recursive Sets."[1][5]

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

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 with probabilistic automata.[1]

In 1969, Rabin introduced

decidable.[6] 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

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.[9]

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

Rabin–Karp string search algorithm, known for its rolling hash.[11]

Rabin's more recent research has concentrated on computer security. He is currently the

Hebrew University. During the spring semester of 2007, he was a visiting professor at Columbia University teaching Introduction to Cryptography
.

Awards and honours

Rabin is a foreign member of the

a member of the French Academy of Sciences, and a foreign member of the Royal Society.

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 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.[15]

In 1995, Rabin was awarded the

Gordon E. Moore, for Computers and Telecommunications.[17] Rabin was awarded an Honorary Doctor of Science from Harvard University in 2017.[18]

Personal life

Rabin has a daughter, computer scientist Tal Rabin.[19]

See also

References

  1. ^
    S2CID 16975542
    .
  2. ^ "Michael O. Rabin". amturing.acm. Retrieved 14 August 2023.
  3. ^ "Michael O. Rabin - Curriculum Vitae" (PDF). Harvard University. Retrieved 31 March 2017.
  4. doi:10.1147/rd.32.0114. Archived from the original on March 4, 2016.{{cite journal}}: CS1 maint: unfit URL (link
    )
  5. ^ 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
  6. JSTOR 1995086
    .
  7. ^ Rabin, MO (1976). "Probabilistic algorithms". Algorithms and Complexity, Proc. Symp. Pittsburgh.
  8. .
  9. ^ Rabin, MO (January 1979). "Digitalized signatures and public-key functions as intractable as factorization" (PDF). MIT Laboratory of Computer Science Technical Report. Archived from the original (PDF) on September 21, 2006. Retrieved 2007-03-15.
  10. ^ Rabin, Michael O. (1981). How to exchange secrets by oblivious transfer (Technical Report TR-81) (PDF). Aiken Computation Laboratory: Harvard University.
  11. S2CID 5734450
    . Retrieved 2007-03-15.
  12. ^ "Michael O. Rabin". www.nasonline.org. Retrieved 2022-05-02.
  13. ^ "APS Member History". search.amphilsoc.org. Retrieved 2022-05-02.
  14. ^ "Michael Oser Rabin". American Academy of Arts & Sciences. Retrieved 2022-05-02.
  15. ^ ACM Turing Award Citation Archived 2012-07-14 at archive.today
  16. ^ "Israel Prize Official Site - Recipients in 1995 (in Hebrew)". Archived from the original on 2008-12-27.
  17. ^ "Dan David Prize Official Site - Laureates 2010". Archived from the original on March 6, 2010.
  18. ^ "Harvard awards 10 honorary degrees". 25 May 2017.
  19. ^ "Tal Rabin". Forbes. Retrieved 26 October 2022.

External links