Michael O. Rabin

Michael Rabin was born in 1931 in Breslau, Germany, now Wroclaw, Poland. His father, a rabbi, moved the family to Palestine in 1935. Michael was given a very good primary education and attended the best high school in Haifa.

Michael related the following story to explain how he became interested in mathematics at about the age of 10 or 11. In the hallway of his school he encountered a few older students attempting to find a proof for an elementary problem in geometry. To his delight, he was able to solve it, and he enjoyed the experience of starting with just a few known facts about a geometrical figure and deducing others that are not obvious. The idea that with thought alone one can prove geometric statements inspired him to study mathematics.

In high school he was taught mathematics by Elisha Netanyahu, the uncle of the later Israeli Prime Minister. Netanyahu was an important mathematician in his own right, and later became a professor at the Technion in Haifa and Dean of the Faculty of Science. While a high school teacher, Netanyahu organized a weekly seminar to teach topics in advanced mathematics to a select group of students. Rabin participated, and quickly learned much more than would be the norm for a student of his age.

Rabin finished high school at the age of 16. Like most of his classmates, he was then drafted into the army to fight for the independence of the then-new state of Israel. He filled the periods of inactivity by reading mathematics textbooks. One by Professor Abraham Fraenkel in Jerusalem was on set theory, and Rabin wrote to him. Fraenkel, impressed by the depth of the correspondence, met with Rabin and later was instrumental in having him mustered out of the military to attend the University of Jerusalem. He was admitted directly into a Master’s degree program to study algebra, and graduated in 1953. His thesis solved a significant open problem that had been proposed by the German mathematician Emmy Noether.

On the strength of the thesis he was admitted to a PhD program at Princeton, where he studied under Alonzo Church and graduated in 1957. After Rabin finished his PhD he was invited by IBM to attend a summer research workshop for a select group of young scientists. It was there that he and Dana Scott collaborated on the famous paper “Finite Automata and Their Decision Problem” [1] that led to their joint Turing Award in 1976.

Automata theory had really begun with the 1943 study of artificial neural networks by Walter Pitts and Warren McCulloch. Others continued this biologically-inspired work. Rabin and Scott moved away from neural networks, and instead used a computational model known as a finite state machine. These theoretical machines, like the Turing machine, move from one state to another depending on the input and the defined transition rules. Finite state machines had been investigated before, but Rabin and Scott considered different kinds. One was a nondeterministic machine that did not just have one possible transition out of each state, but had several. Essentially the machine could, upon accepting an input symbol, replicate itself, and then each machine would proceed with the computation along one of the possible transitions. As noted in the citation for the Turing Award, this concept of a nondeterministic machine has proven to be extremely valuable in the theoretical investigation of many problems, and continues to be an inspiration for new work.

The next summer Rabin was again invited to the IBM research workshop.  He met another future Turing Award recipient, John McCarthy, who explained a puzzle to him about spies and guards. The spies have passwords that allow them to pass from enemy territory to their own. The guards cannot be trusted to keep the passwords secret, so some method had to be found to verify that even if the enemy gains knowledge of the password, the spies can safely return but the enemy infiltrators are kept out. One solution came from the middle-square method, which had been proposed by mathematician John von Neumann as a way of generating random numbers. Each spy is given a 100-digit number x, and the guards are given another 100-digit number obtained by taking the middle digits from x². When returning, the spy gives the guard x. The guard then computes x² and compares the middle digits to the number he possesses as a pass code. Even if the guard passes his number to an enemy, it is very difficult for the enemy to determine what initial number resulted in those 100 middle digits of x².

Rabin began thinking in general about functions that are difficult to invert —in this case computing the original number x knowing only the middle digits of x². His study resulted in the groundbreaking paper [2] “Degree of Difficulty of Computing a Function and a Partial Ordering of Recursive Sets”,  which was the starting point for his later advances in the theoretical study of computational complexity particularly in relation to cryptography.

Rabin had returned to the University of Jerusalem, first as a senior lecturer, then as Associate Professor, and then Professor. He kept up his prodigious research output while also becoming chairman of their Institute of Mathematics, chairman of the Department of Computer Science, and Rector (academic head) of the entire University.

In 1975, having finished his term at Rector, he went to MIT as a Visiting Professor and worked on primality testing with Gary Miller. This involves determining if a very large number is prime—whether the number has no divisors other than itself and 1. Miller had earlier developed a primality test that was based on the unproven Riemann hypothesis. That bothered Rabin, because if the Riemann hypothesis was eventually shown to be false it would bring into question any methods based on it. Michael had earlier worked on probabilistic automata, theoretical machines for which a random number is used to determine which transition to take from each state. While not deterministic in the sense that it always provides a provable result, if run a number of times the chance of it being incorrect can be made vanishingly small. Rabin used this concept to develop a primality testing algorithm [3] called the Miller-Rabin test. It was later shown to be deterministic: it is guaranteed to work if a certain number of tests were done.

Adding randomness to algorithms was to be a theme for much of Rabin’s later work on many different problems. One of his favorites, the four-square problem that had first been discussed by Joseph-Louis Lagrange in 1770, was how to express an integer as the sum of four squares: for any integer y find four not necessarily unique, integers a, b, c, d such that y = a² + b² + c² + d². Lagrange had shown that it is always possible, but nobody knew an efficient algorithm to find a, b, c and d. In speaking to a class of students at MIT in 1977 Rabin proposed a randomized algorithm, which he and Jeff Shallit later published as part of a larger study of randomized algorithms [4]. 

Rabin’s later work concerns cryptographic problems for preventing piracy on the internet. Recently he has been examining how to ensure the privacy and secrecy of online auctions. In auctions like those conducted by Google for advertising slots, the participants want their identity and bidding strategy to remain anonymous, but want to be assured that the results of the auction are fair. Rabin has worked as a consultant to create a zero-knowledge proof that gives such assurances.