Michael O. Rabin
search externally:   Google Scholar,   Springer,   CiteSeer,   Microsoft Academic Search,   Scirus ,   DBlife


Rabin’s fundamental innovations in computer science include: Non-Deterministic computations, with D. Scott; Probabilistic automata; complexity of computations; automata on infinite trees leading to applications to temporal programs verification; randomized algorithms, including primality testing, algorithms for finite fields, Rabin-Karp string matching algorithms, randomized Byzantine Agreement protocols; Rabin public-key encryption provably as safe as factorization; Oblivious Transfer; provably unbreakable encryption systems; practically efficient zero-knowledge proofs with applications to auctions and financial processes.

Rabin got his PH.D. under Alonzo Church at Princeton University where he had his first academic appointment. Kurt Gödel invited him to the Institute for Advanced Study. Rabin was professor of mathematics at the Hebrew University. He was Rector (academic head) at HU 1972-1975. Since 1981 he is professor of computer science at Harvard University. At various times he held Visiting Professorships at Yale University, the Weizmann Institute, The Technion, UC Berkeley, M.I.T., University of Paris, the Courant Institute of Mathematics, Caltech, ETH Zurich, Columbia University, and Kings College, London. He was Saville Fellow at Merton College, Oxford, and Steward Fellow at Gonville and Caius College, Cambridge. From 1982 to 1994 he served on the IBM Science Advisory Committee. During Spring of 2009 he was Visiting Researcher at Google.

His contributions were recognized by numerous awards including:

Rothschild Prize in Mathematics; The ACM Turing Award in Computer Science; Harvey Prize for Science and Technology; Israel Prize in Computer Science; ACM Kanellakis Theory and Practice Award; E.M.E.T. Prize in Computer Science; IACR Fellow; Dan David Prize in Computing and Communications.

Rabin was elected member or foreign honorary member to academies including: the American Academy of Arts and Sciences (1975- ), the Israel Academy of Sciences and Humanities (1982- ), the US National Academy of Sciences (1984- ), the American Philosophical Society (1988- ), the French Academy of Sciences (1995- ), Foreign Member of the Royal Society (2007-) and Member of the European Academy of Science (2007-). He holds honorary degrees from six universities.


invited talk
flag Turing, Church, Gödel, Computability, Complexity and Randomization: A Personal View
as author at  Alan Turing Centenary Conference Manchester, 2012,