Michael O. Rabin
Michael Oser Rabin | |
|---|---|
| Born | September 1, 1931 Breslau, Germany (now Wrocław, Poland) |
| Occupation(s) | Mathematician, Computer Scientist |
| Known for | Turing Award, Nondeterministic automata, Miller–Rabin primality test, Rabin signature algorithm, Rabin–Karp string search algorithm |
| Awards | Turing Award (1976), Israel Prize (1995), Dan David Prize (2010), Honorary Doctorate of Science from Harvard University (2017) |
Michael Oser Rabin (; born September 1, 1931) is an Israeli expert in mathematics and computer science, honored with the prestigious Turing Award.
Early life and education
Born in 1931 in Breslau, then part of the Germany (currently Wrocław, Poland), Rabin was the son of a rabbi. In 1935, he and his family relocated to Mandatory Palestine. Demonstrating exceptional talent in mathematics from a young age, he studied under mathematician Elisha Netanyahu while attending a leading high school in Haifa.
He completed his studies at the Hebrew Reali School in 1948 before being conscripted into the military during the 1948 Arab–Israeli War. Following advocacy by mathematician Abraham Fraenkel, Rabin was released from service in 1949 to pursue higher education. He obtained an M.Sc degree from the Hebrew University of Jerusalem, commenced graduate studies at the University of Pennsylvania, and finalized his doctoral degree at Princeton University in 1956.
Career
Rabin held positions as Associate Professor of Mathematics at both the University of California, Berkeley (1961–62) and MIT (1962–63) prior to his appointment as Gordon McKay Professor of Computer Science at Harvard University in 1981. Before these roles, he was a faculty member at Hebrew University.
During the late 1950s, Rabin worked at IBM’s Lamb Estate research facility, where together with Dana Scott, he authored "Finite Automata and Their Decision Problems." This seminal paper introduced nondeterministic automata as a fundamental concept within computational theory. Their research laid groundwork for computational complexity theory, especially regarding the complexity classes P and NP.
Upon returning to Jerusalem, Rabin directed the Institute of Mathematics at Hebrew University, promoting advances in logic and foundational computer science despite limited acknowledgment from contemporaneous mathematicians. In 1960, while at Bell Labs, he pioneered the concept of probabilistic automata, illustrating that these models could achieve exponentially fewer states than deterministic counterparts.
In 1966, Rabin independently formulated the concept of polynomial time, alongside contemporaries Alan Cobham (mathematician) and Jack Edmonds. By 1969, he developed infinite-tree automata and established decidability results within monadic second-order logic, significantly influencing both automata theory and formal logic.
After serving as Rector of Hebrew University until 1975, Rabin took a visiting professorship at the Massachusetts Institute of Technology. There, he created the Miller–Rabin primality test, a probabilistic algorithm essential for rapid primality verification without reliance on unproven assumptions. This breakthrough forms a cornerstone of modern public-key cryptography and earned him and collaborators the Paris Kanellakis Award in 2003.
In 1976, Rabin unveiled this primality test at Carnegie Mellon University, where it was acclaimed as "revolutionary." Two years later, he introduced the Rabin signature algorithm, marking the first asymmetric cryptosystem with security rigorously linked to the complexity of integer factorization.
In 1981, Rabin reintroduced a form of oblivious transfer, facilitating secure message delivery with probabilistic knowledge on the receiver’s part. In collaboration with Richard Karp in 1987, he developed the efficient Rabin–Karp string search algorithm, distinguished by its innovative rolling hash method.
More recently, his research has concentrated on computer security. Rabin holds emeritus status at both Harvard and Hebrew University and served as a visiting professor at Columbia University in 2007, where he taught Introduction to Cryptography.
Awards and honours
Rabin holds foreign membership in several prestigious institutions, including the United States National Academy of Sciences, the American Philosophical Society, the American Academy of Arts and Sciences, the French Academy of Sciences, as well as the Royal Society.
In 1976, Rabin, together with Dana Scott, was honored with the Turing Award for their groundbreaking 1959 publication that introduced nondeterministic machines—a pivotal idea that has continued to influence computer science research profoundly.
He was the recipient of the Israel Prize in computer sciences in 1995. Later, in 2010, Rabin was recognized with the Dan David Prize in the "Future" category by Tel Aviv University, sharing this accolade with Leonard Kleinrock and Gordon E. Moore for their significant impact on Computers and Telecommunications. Additionally, Harvard University conferred upon him an Honorary Doctorate of Science in 2017.
Personal life
Rabin is the father of computer scientist Tal Rabin.
See also
- Oblivious transfer
- Rabin automaton
- Rabin fingerprint
- Hyper-encryption
- List of Israel Prize recipients