Michael O. Rabin

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.

In 1995, Rabin was awarded the Israel Prize, in computer sciences. 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. Rabin was awarded an Honorary Doctor of Science from Harvard University in 2017.

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.

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 1979, Rabin invented the Rabin cryptosystem, the first asymmetric cryptosystem whose security was proved equivalent to the intractability of integer factorization.

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."

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:

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. 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 1969, Rabin introduced infinite-tree automata and proved that the monadic second-order theory of n successors (S2S when n = 2) is decidable. A key component of the proof implicitly showed determinacy of parity games, which lie in the third level of the Borel hierarchy.

Rabin became Associate Professor of Mathematics at the University of California, Berkeley (1961–62) and 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.

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.

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". Soon, using nondeterministic automata, they were able to re-prove Kleene's result that finite state machines exactly accept regular languages.

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.

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

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.