Rabin has sadly just passed away at 94. This is a short piece on honoring him immediately. More is planned for the future.
His work has touched key areas of mathematics as well as central areas of computer theory. Without his work theory would be completely different today. Michael’s work is an incredible mine with three rich veins. There are deep, hard theorems—for instance his work on the second-order theory of two successors. There is foundation creation—for instance his work on finite automata with Dana Scott, which was awarded the 1976 Turing award. And there is practical work—for example his beautiful string matching algorithm with Richard Karp, and much more. His concept of oblivious transfer is a bedrock primitive in secure computation. Not surprisingly he has been honored with many prizes, including the Turing Award, the Israel Prize, the Emet Prize, the Harvey Prize, the Dan David Prize, and others.
Michael Rabin Was Brilliant
Rabin showed over and over how brilliant he was. He found new ways to compute things, things that were important. Without his work whole fields would never have been possible. Almost all his work was on finding faster algorithms for such key problems. Perhaps all his work was on algorithms.
Generally he pioneered randomization as a key tool to solve critical, important problems, and he set the trend. His leadership in this respect that randomization is a fundamental algorithmic tool, practice, and then as a resource, is perhaps even more important than his individual technical contributions. He seemed to really have had the insight that randomization was going to be important, and made it so. Here are just a few examples of this terrific work.
Number Theory
Rabin used randomization to determine whether a number is prime. His insight was based on Gary Miller’s earlier work that uses deep unproven versions of the Riemann hypothesis. It is unimaginable what our world would be like today if such algorithms in number theory did not exist. Modern cryptography would be impossible without Rabin’s brilliant insight. He made this whole area possible.
String Theory
His work with Dick Karp used randomization to change forever how people think about string matching and related questions. This changed this important area forever. Their work made string algorithms possible—which changed this whole area of important work.
Geometric Theory
Rabin also used his random methods to solve basic geometry problems. Donald Knuth in volume 3 of The Art of Computer Programming (1973) called it the post-office problem. Later it became the nearest neighbor problem. Rabin showed that there was an algorithm for finding the nearest neighbor problem in linear time.
Even decades later there are still exciting questions about his algorithm and related methods. Perhaps it shows that Rabin was brilliant also when his methods were not perfect. He created new ways to look at such basic geometric problems. That these methods still need to be studied is a tribute to his leadership.
How We Should Honor Michael Rabin Forever
The theory community is planning a longer more technical piece on Rabin’s wonderful work. But we should begin now to think about how to honor Rabin. There are several ways that we might do this.
Prizes: We could create prizes in his honor. I cannot imagine that it would not be a great honor to get a prize that existed for work that advances methods he started. Perhaps the Rabin-Randomization Prize?
Conferences: We certainly could create special conferences or talks at existing conferences in his honor. Rabin was famous for his terrific talks that explained his work with such clarity. Having special talks in his honor would be cool.
Other: Perhaps other ideas can be advanced. What do you think?
Finally I wish to thank Jin-Yi Cai for invaluable comments on this piece.
Rabin was a great lecturer. Maybe made a archive of his video recorded lectures available. His course notes and talks should also be preserved. Maybe ACM can make a archive of all his papers, slides and recorded talks.