Michael Oser Rabin (Hebrew:מִיכָאֵל עוזר רַבִּין; born September 1, 1931) is an Israelimathematician,computer scientist, and recipient of theTuring Award.
Rabin was born in 1931 inBreslau,Germany (todayWrocław, inPoland), the son of arabbi. In 1935, heemigrated with his family toMandatory Palestine. As a young boy, he was very interested in mathematics and his father sent him to the best high school inHaifa, where he studied under mathematicianElisha Netanyahu, who was then a high school teacher.[1]
Rabin graduated from theHebrew Reali School in Haifa in 1948, and was drafted into the army during the1948 Arab–Israeli War. The mathematicianAbraham Fraenkel, who was a professor of mathematics inJerusalem, intervened with the army command, and Rabin was discharged to study at the university in 1949.[1] Afterwards, he received an M.Sc fromHebrew University of Jerusalem. He began graduate studies at theUniversity of Pennsylvania before receiving aPh.D. fromPrinceton University in 1956.[2]
Rabin became Associate Professor of Mathematics at theUniversity of California, Berkeley (1961–62) andMIT (1962-63). Before moving toHarvard 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 forIBM at the Lamb Estate inWestchester County, New York with other promising mathematicians and scientists. It was there that he andDana Scott wrote the paper "Finite Automata and Their Decision Problems".[4] Soon, using nondeterministic automata, they were able to re-proveKleene's result that finite state machines exactly accept regular languages.[1]
As to the origins of what was to becomecomputational 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]
Nondeterministic machines have become a key concept in computational complexity theory, particularly with the description of thecomplexity classes P and NP.
Rabin then returned to Jerusalem, researching logic, and working on the foundations of what would later be known ascomputer 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 byEdward F. Moore to work atBell Labs, where Rabin introducedprobabilistic 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 1966 (published in conference proceedings in 1967),[6] Rabin introduced the notion of polynomial time (introduced independently and very shortly before by Cobham[7] and Edmonds[8]).
In 1969, Rabin introduced infinite-tree automata and proved that the monadic second-order theory ofn successors (S2S whenn = 2) isdecidable.[9] A key component of the proof implicitly showeddeterminacy ofparity games, which lie in the third level of theBorel hierarchy.
In 1975, Rabin finished his tenure as Rector of the Hebrew University of Jerusalem and went to theMassachusetts Institute of Technology in the USA as a visiting professor. While there, Rabin invented theMiller–Rabin primality test, a randomized algorithm that can determine very quickly (but with a tiny probability of error) whether a number isprime.[10][11] Rabin's method was based on previous work ofGary Miller that solved the problem deterministically with the assumption that thegeneralized 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, andVolker Strassen were given theParis Kanellakis Award for their work on primality testing.
In 1976 he was invited byJoseph Traub to meet atCarnegie Mellon University and presented the primality test, which Traub called "revolutionary".[1]
In 1978, Rabin invented theRabin signature algorithm, the first asymmetric cryptosystem whose security was proved equivalent to the intractability ofinteger factorization.[12][13]
In 1981, Rabin reinvented a weak variant of the technique ofoblivious transfer invented by Wiesner under the name of multiplexing,[14] 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 withRichard Karp, created one of the most well-known efficientstring search algorithms, theRabin–Karp string search algorithm, known for itsrolling hash.[15]
Rabin's more recent research has concentrated on computer security. He is currently theThomas J. Watson Sr. Professor of Computer Science, Emeritus atHarvard University and Professor of Computer Science (Emeritus) atHebrew University. During the spring semester of 2007, he was a visiting professor atColumbia University teachingIntroduction toCryptography.
Rabin is a foreign member of theUnited States National Academy of Sciences,[16] a member of theAmerican Philosophical Society,[17] a member of theAmerican Academy of Arts and Sciences,[18] a member of theFrench Academy of Sciences, and a foreign member of theRoyal Society.
In 1976, theTuring Award was awarded jointly to Rabin andDana 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.[19]
In 1995, Rabin was awarded theIsrael Prize, in computer sciences.[20] In 2010, Rabin was awarded theTel Aviv UniversityDan David Prize ("Future" category), jointly withLeonard Kleinrock andGordon E. Moore, for Computers and Telecommunications.[21] Rabin was awarded an Honorary Doctor of Science from Harvard University in 2017.[22]
Rabin has a daughter, computer scientistTal Rabin.[23]
