Michael Rabin passed away on April 14,2026. I blogged about him here.
My post listed results of his that proved upper and lower bounds on problems. My point was that he proved upper and lower bounds for MANY different levels- from decidable to regular. And I am sure I left out some of his results.
Here are some things I did not mention.
1) Rabin and Scott shared the Turing Award in 1976. My not mentioning it raises the following question:
If I want to say someone has an impressive set of results what is a better way:
listing the awards they've won, or
listing their results.
I leave this to the reader.
2) I had Rabin for two graduate courses at Harvard: Algorithms and Complexity Theory. He was a great teacher and gave insights to the results, some of which he had either proven or worked on.
3) I recalled thanking him in my PhD Thesis. So I dusted it off to see what I had said:
The many courses I have taken at Harvard and MIT have helped me create this thesis. I am especially indebted to Michael Rabin, Mike Sipser, and Michael Stob for their excellent courses in algorithms, complexity theory, and recursion theory. Their pedagogy has been an inspiring example of what good teaching can and should be.
What is the probability that all three great teachers were named Michael? I do not know, however, I suspect Michael Rabin could have told me.
