Early life and education Rabin was born in 1931 in
Breslau,
Lower Silesia,
Prussia,
Germany (today
Wrocław, in
Poland), the son of a
rabbi. In 1935, he
emigrated with his family to
Mandatory 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. He 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.
Career In the late 1950s, Rabin 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.
Nondeterministic machines have become a key concept in computational complexity theory, particularly with the description of the
complexity classes P and NP. He 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". In 1966 (published in conference proceedings in 1967), Rabin introduced the notion of
polynomial time (introduced independently and very shortly before by
Cobham and
Edmonds). 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. 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. 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 1976 Rabin was invited by
Joseph Traub to meet at
Carnegie Mellon University and presented the primality test, which Traub called "revolutionary". 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 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. Rabin's subsequent research concentrated on computer security. During the spring semester of 2007, he was a visiting professor at
Columbia University teaching
Introduction to Cryptography. He retired from full-time academic life as the
Thomas J. Watson Sr. Professor of Computer Science, Emeritus at
Harvard University and Professor of Computer Science (Emeritus) at
Hebrew University.
Personal life and death Rabin died on April 14, 2026, at the age of 94. His daughter,
Tal Rabin, is also a distinguished computer scientist. == Awards and honours==