Right. Another name to document. Don't expect poetry. This is about facts, meticulously laid out, like specimens under glass. And if you find it dry, well, that's the point. It's not meant to be a carnival.
Michael Oser Rabin
מִיכָאֵל עוזר רַבִּין
Born September 1, 1931, in Breslau, Germany (now Wrocław in Poland). The son of a rabbi, a lineage that perhaps explains a certain… gravity. He was already showing an interest in mathematics as a boy. So much so that his father, not content with the usual tutelage, sent him to the best high school in Haifa. There, he encountered Elisha Netanyahu, who, at the time, was merely a high school teacher, but clearly recognized something in the young Rabin. [1]
He finished his schooling at the Hebrew Reali School in Haifa in 1948. Then came the rather inconvenient interruption of the 1948 Arab–Israeli War. Drafted, naturally. But Abraham Fraenkel, a mathematics professor in Jerusalem, apparently saw the potential and intervened. Rabin was discharged to study at the university in 1949. [1] He eventually earned an M.Sc from Hebrew University of Jerusalem. Graduate work followed at the University of Pennsylvania, culminating in a Ph.D. from Princeton University in 1956. [2] A trajectory, you see. Precise.
Career
Rabin's academic journey took him to the University of California, Berkeley as an Associate Professor of Mathematics from 1961 to 1962, and then to MIT from 1962 to 1963. Before settling in as the Gordon McKay Professor of Computer Science at Harvard University in 1981, he held a professorship at the Hebrew University. [3]
In the late 1950s, a summer research stint for IBM at the Lamb Estate in Westchester County, New York proved… productive. He joined other promising minds, and it was there that he and Dana Scott penned "Finite Automata and Their Decision Problems." [4] Using nondeterministic automata, they managed to re-prove Stephen Cole Kleene's established result: that finite state machines indeed accept regular languages. [1] A neat piece of work.
The following summer, back at the Lamb Estate, Rabin delved into what would become computational complexity theory. John McCarthy presented him with a puzzle involving spies, guards, and passwords. Rabin, predictably, studied it. The result was an article, "Degree of Difficulty of Computing a Function and Hierarchy of Recursive Sets." [1] [5]
The concept of nondeterministic machines, a product of this period, has since become fundamental to computational complexity theory, particularly in the context of the complexity classes P and NP.
He returned to Jerusalem, focusing on logic and the nascent foundations of what we now call computer science. At 29, he was Associate Professor and head of the Institute of Mathematics at the Hebrew University. By 33, he was a full professor. Rabin himself recalls the climate: "There was absolutely no appreciation of the work on the issues of computing. Mathematicians did not recognize the emerging new field." [1] A familiar refrain, no doubt.
In 1960, Edward F. Moore invited him to Bell Labs. There, Rabin introduced probabilistic automata – machines that use coin tosses to determine state transitions. He demonstrated how regular languages, which might require an immense number of states in a deterministic model, could be represented with an exponential reduction in states using probabilistic automata. [1]
In 1966 (published in conference proceedings in 1967), [6] Rabin introduced the notion of polynomial time. This was a concept independently and very shortly before developed by Alan Cobham [7] and Jack Edmonds. [8]
Then, in 1969, Rabin introduced infinite-tree automata. He proved that the monadic second-order theory of n successors—specifically S2S when n=2—is decidable. [9] A crucial part of this proof implicitly demonstrated the determinacy of parity games, placing them within the third level of the Borel hierarchy.
After concluding his tenure as Rector of the Hebrew University of Jerusalem in 1975, Rabin moved to the Massachusetts Institute of Technology as a visiting professor. It was during this period that he developed the Miller–Rabin primality test. This randomized algorithm allows for very rapid determination of whether a number is prime, albeit with a minuscule probability of error. [10] [11] Rabin's approach was built upon the prior work of Gary Miller, which required the assumption of the generalized Riemann hypothesis for its deterministic solution. Rabin's version, however, made no such assumptions. The efficiency of primality testing is a cornerstone of most public-key cryptography. In recognition of their contributions, Miller, Rabin, Robert M. Solovay, and Volker Strassen received the Paris Kanellakis Award in 2003.
In 1976, Joseph Traub invited Rabin to Carnegie Mellon University to present his primality test. Traub, impressed, described it as "revolutionary." [1]
The year 1978 saw Rabin invent the Rabin signature algorithm. This was the first asymmetric cryptosystem whose security could be proven equivalent to the difficulty of integer factorization. [12] [13]
In 1981, Rabin revisited the concept of oblivious transfer, first conceived by Wiesner. He reinvented a weaker variant under the name of multiplexing, [14] enabling a sender to transmit a message to a receiver with a controlled probability of the receiver learning it, without the sender being aware of the outcome.
Collaborating with Richard Karp in 1987, Rabin developed one of the most widely recognized efficient string search algorithms: the Rabin–Karp string search algorithm, notable for its use of a rolling hash. [15]
More recently, Rabin's research has focused on computer security. He currently holds the title of Thomas J. Watson Sr. Professor of Computer Science, Emeritus, at Harvard University and Professor of Computer Science (Emeritus) at Hebrew University. In the spring of 2007, he was a visiting professor at Columbia University, where he taught an introductory course on Cryptography.
Awards and Honours
Rabin is recognized internationally. He is a foreign member of the United States National Academy of Sciences, [16] a member of the American Philosophical Society, [17] and the American Academy of Arts and Sciences. [18] His affiliations extend to the French Academy of Sciences and he is a foreign member of the Royal Society.
In 1976, the prestigious Turing Award was jointly presented to Rabin and Dana Scott. The citation acknowledged their 1959 paper, "Finite Automata and Their Decision Problems," for introducing the concept of nondeterministic machines—a concept that proved to be "an enormously valuable concept" and a "continuous source of inspiration for subsequent work in this field." [19]
Rabin was honored with the Israel Prize in computer sciences in 1995. [20] In 2010, he shared the Tel Aviv University Dan David Prize ("Future" category) with Leonard Kleinrock and Gordon E. Moore for their work in Computers and Telecommunications. [21] Harvard University awarded him an Honorary Doctor of Science in 2017. [22]
Personal Life
Rabin has a daughter, Tal Rabin, who is also a computer scientist. [23]