About the Speaker

Michael O. Rabin

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.

Turing, Church, Gödel, Computability, Complexity and Randomization: A Personal Perspective

The above named have innovated the concept of computability in the mid ninety-thirties. Alan Turing gave his definition of computability via a creation of a model of a universal stored program computer. The distinction between computable and non-computable functions was subsequently refined by a discussion of the inherent complexity of computable functions. The speaker will draw from his personal interaction with Church, Gödel and the people working with John von-Neumann a picture of the evolution of computing as well as give a perspective of the future of computer science and technology.