In Memoriam: Michael O. Rabin
Michael O. Rabin, Member (1958) in the School of Mathematics, passed away on April 14, 2026, in Jerusalem, Israel, at the age of 94. An obituary shared by the Communications of the Association for Computing Machinery (ACM), who awarded Rabin the A.M. Turing Award in 1976, described the influential scholar's contributions as having "touch[ed] nearly every aspect of computing."
Born in Breslau, Germany (now Wrocław, Poland), in 1931, Rabin went on to earn his Ph.D. from Princeton University in 1957 before joining the faculty of Hebrew University of Jerusalem in 1958. During his distinguished career, he also served on the faculty of Harvard University, and was elected Hebrew University’s rector—their chief academic officer—in 1942. Widely recognized as a computer science pioneer, his visionary research established foundational principles in modern algorithms, cryptography, and artificial intelligence.
The obituary highlights Rabin's time at IAS as being key to one of his most important breakthroughs, namely the birth of complexity theory:
"Kurt Gödel [Professor (1953–78) in the School of Mathematics] invited Rabin to the Institute for Advanced Study, where the two met weekly through 1958. Rabin later described those sessions as 'incredibly illuminating.' Rabin returned to IBM’s summer research program and shifted his focus from the question of 'what is computable?' to the question of how costly computation might be. He proved that for every computable function, there exists another function that is provably more difficult to compute, thus establishing a genuine hierarchy of computational difficulty independent of hardware or programming language. A key realization was that complexity is 'inherent in the task.' Many point to Rabin’s 1960 publication as the birth of what is now called complexity theory."
Avi Wigderson, Herbert H. Maass Professor in the School of Mathematics and fellow ACM A.M. Turing Award recipient, offered this distinct tribute to Rabin, his colleague at Hebrew University for 15 years:
"Michael Rabin was a titan, one of the founding fathers of the theory of computation. His central contributions to almost every subfield, including automata theory, computational complexity, randomized algorithms, cryptography, verification, distributed systems, and more, have shaped and propelled these areas. His contributions include many gems that will forever remain in textbooks and courses. His infectious enthusiasm about computation and its centrality to science, technology, and society has inspired generations of students and researchers alike."
Read the obituary in full on the Communications of the ACM website.
