Michael O. Rabin
Born 1 September 1931 in Breslau, Germany (today Wrocław, Poland)
Turing Award (1976) “with Dana S. Scott, for their joint paper ‘Finite Automata and Their Decision Problems,’ which introduced the idea of nondeterministic machines, which has proved to be an enormously valuable concept. Their (Scott & Rabin) classic paper has been a continuous source of inspiration for subsequent work in this field.”
Michael O. Rabin, the son of a Judaic Scholar, emigrated to Palestine in 1935 and received an excellent mathematical education there. After his military service he was admitted to master’s studies in Mathematics at the Hebrew University in Jerusalem (Master of Science 1953). He received his Ph.D. in Mathematics under Alonzo Church at Princeton University in 1957 and spent a year at the Institute for Advanced Study at Kurt Godel’s invitation. He then worked as a Fine Instructor at Princeton University, USA (1956-58) and a member of the Institute for Advanced Study, Princeton (1958), but returned that year to Jerusalem as a lecturer at the Hebrew University, later becoming an associate professor and professor (from 1965). He was Albert Einstein Professor at the Hebrew University from 1980 to 1999 where he was also Rector (academic head) from 1972 to 1975. From 1983 to 2012 he was T.J. Watson Sr. Professor of Computer Science at Harvard University. He was Visiting Professor at Berkeley, Columbia, Yale, Paris University, University College London, MIT, Cal Tech, ETH, NYU Courant Institute. He was Saville Fellow at Merton College Oxford and Steward Fellow at Gonville and Caius College Cambridge. During spring 2009 he was Visiting Researcher at Google Lab New York. Today, Michael Rabin is Research Professor of Computer Science at Harvard SEAS and Professor of Computer Science at Columbia University.
Rabin’s awards include the ACM Turing Award, the Dan David Prize in Computation and Communication, the Israel Prize in Computer Science, the EMET Prize in Computer Science, the Harvey Prize in Science and Technology, the ACM Paris Kanellakis Prize for Theory and Practice, and the Rothschild Prize in Mathematics. He is IACR Fellow. His academy memberships include the National Academy of Sciences, The American Academy of Arts and Sciences, the American Philosophical Society, the French Academy of Sciences, the Royal Society and the Israel Academy of Sciences. He holds six honorary degrees.
Rabins contributions include innovation of non-deterministic computations, probabilistic automata, the first paper on complexity of computations, non-deterministic automata on infinite trees applicable to decision problems in logic and program verification, randomized algorithms – including a randomized test for primality, the elegant “Miller-Rabin test” for primality from 1980 – and randomized algorithms for string matching, PKE system provably as safe as factorization, oblivious transfer, randomized algorithm for the Byzantine Agreement problem, asynchronous parallel computing, a practical provably unbreakable encryption system (the so called “Rabin cryptosystem”) recently implemented by a MIT student jointly supervised by Rabin and Ron Rivest. In the Rabin cryptosystem, data is encrypted with a public key so that only the owner of a private (secret) key can decrypt it again. Currently Rabin is working on a practically efficient zero-knowledge proof system with application to privacy and to financial processes such as secure auctions, matching problems, and regulation compliance.