Nature is our source of randomness: on the death of Michael O. Rabin

Michael O. Rabin was born in Breslau on September 1, 1931, the son of Rabbi Israel Rabin and writer Ester Rabin. The family emigrated to Mandatory Palestine in 1935. His interest in mathematics was fostered by his teacher Elisha Netanyahu, who included him in a small group of interested students. When he was to be drafted into the army at the age of 16 in the 1948 Arab-Israeli War, the famous mathematician Abraham Fraenkel advocated for his continued education at the university. In 1952, Rabin completed his studies with a master's thesis on a problem discovered by Emmy Noether, which earned him a scholarship at Princeton University. There, he studied with Dana Scott under Alonzo Church, under whom Alan Turing had also studied.

Fundamental Works

In the summer of 1957, Rabin and Scott were invited by IBM, where they wrote the paper on “Finite Automata and Their Decision Problems,” in which they dealt with the neural networks (as they are called today) of Warren McCulloch and Walter Pitts. In 1956, the logician Stephen Cole Kleene had introduced the class of regular languages into computer science with his theorem, and therefore Rabin and Scott were able to confirm Kleene's assumptions with their work on non-deterministic automata. “We didn't actually have any deeper philosophical reason to consider this non-determinism, although, as we know today, it is at the heart of the P = NP question – a problem of immense practical and theoretical importance. For us, it was just one of several variants,” Rabin said in an interview about his life, which he granted to his student Dennis Shasha. In 1976, he and Scott received the Turing Award for this work, which remains the subject of lively discussions to this day.

After this episode, Rabin became involved with cryptographic problems, inspired by a problem posed to him by John McCarthy: How can a spy who states their password be reliably identified by a guard who is supposed to calculate the password? The answer was Rabin's paper “Probabilistic Algorithm for Testing Primality.” The primality test, known today as the Miller-Rabin test, quickly provides the answer to whether a number is prime with a probability of 99.9 percent after six tests for long numbers, and is therefore used in many cryptographic applications. With his paper “Digitalized Signatures and Public-Key Functions as Intractable as Factorization,” Rabin laid the groundwork for the Rabin cryptosystem in 1979, which, unlike the primality test, is hardly used.

Later, after years of research and teaching at the Hebrew University, where he was temporarily rector, Rabin was back at IBM from 1982 and was a member of the Science Advisory Committee there until 1994. In 1987, he and Richard M. Karp developed the Rabin-Karp algorithm, which features an efficient hashing method for searching for plagiarism. In the interview about his life, he describes how important the role of randomness has been for his work. “The influence of randomness on so many algorithmic problems is completely baffling to me. It's efficient, it works; but why and how is an absolute mystery to me. Algorithms in their pure form require a physical source of randomness. So it's a kind of collaboration between us computer scientists and nature as the source of randomness. That's unique and raises some questions in physics and philosophy.”

(wpl)