Die Laureaten

Copyright © Klaus Tschira Stiftung / Peter Badge

Michael O. Rabin

geboren am 1. September 1931 in Breslau (Deutsches Reich; heute Wroclaw, Polen)

Turing Award (1976) „zusammen mit Dana S. Scott für ihren gemeinsamen Aufsatz ‘Finite Automata and Their Decision Problem’, der die Idee der nichtdeterministischen Maschinen einführte, ein Konzept, das sich inzwischen als enorm wertvoll erwiesen hat. Das klassische Paper von Rabin und Scott wurde eine beständige Inspirationsquelle für die folgende Forschung auf diesem Gebiet.“

Michael O. Rabin, Sohn eines Jüdischen Lehrers, musste 1935 nach Palästina emigrieren. Dort erhielt er eine exzellente mathematische Ausbildung. Nach seinem Militärdienst wurde er direkt zu einem Masterstudium in Mathematik an der Hebrew University in Jerusalem (Master of Science 1953) zugelassen. Er promovierte bei Alonzo Church an der Princeton University (Ph.D. 1957) und verbrachte auf Kurt Gödels Einladung ein Jahr am Institut for Advanced Study. Anschließend arbeitete er als Lehrbeauftragter (Fine Instructor) an der Princeton University, USA, (1956-58) und als Mitglied des Institute for Advanced Study, Princeton (1958), kehrte aber im selben Jahr nach Jerusalem zurück, um an der Hebrew University als Dozent, außerordentlicher Professor und schließlich als Professor zu arbeiten (ab 1965); von 1980 bis 1999 hielt er den Albert Einstein Lehrstuhl der Hebrew University und Rektor der Universität von 1972-75. Von 1983 bis 2012 war er Thomas J. Watson Sr. Professor für Informatik an der Harvard University. Er war außerdem Gastprofessor an den Universitäten Berkeley, Columbia, Yale, Paris, am University College London, am MIT, dem Cal Tech, der ETH sowie dem NYU Courant Institute. Er war Saville Fellow am Merton College Oxford und Steward Fellow am Gonville and Caius College, Cambridge. Im Frühjahr 2009 war er Gastprofessor am Google Lab New York. Heute ist Michael Rabin Research Professor für Informatik am Harvard SEAS und Professor für Informatik an der Columbia University.

Rabin erhielt unter anderem den ACM Turing Award, den Dan David Prize in Computation and Communication, den Israel Prize in Computer Science, den EMET Prize in Computer Science, den Harvey Prize in Science and Technology, den ACM Paris Kanellakis Prize for Theory and Practice sowie den Rothschild Prize in Mathematik. Er ist IACR Fellow und unter anderem Mitglied in der amerikanischen National Academy of Sciences, der American Academy of Arts and Sciences, der American Philosophical Society, der französischen Akademie der Wissenschaften, der Royal Society und der Israel Academy of Sciences. Er hat sechs Ehrendoktortitel.

Michael Rabin leistete unter anderem Beiträge bei der Einführung nicht-deterministischer Berechnungen, probabilistischer Automaten, er verfasste die erste Arbeit über die Berechnungs-Komplexität, entwickelte nicht-deterministische Automaten auf unendlichen Bäumen mit Anwendungen für Entscheidungsprobleme in der Logik und die Verifizierung von Programmen, randomisierte Algorithmen – darunter einen randomisierten Primzahltest, den eleganten “Miller-Rabin-Test” für die Primzahleigenschaft aus dem Jahr 1980 – und randomisierte Such-Algorithmen für Zeichenketten. Er erfand ein public-key-Verschlüsselungs-System, das beweisbar so sicher ist wie Faktorisierung, oblivious transfer, einen randomisierten Algorithmus für das Problem der byzantinischen Generäle, asynchrones paralleles Rechnen, ein in der Praxis beweisbar unknackbares Verschlüsselungssystem (das so genannte “Rabin cryptosystem”), das jüngst von einem MIT-Studenten implementiert wurde, unter der gemeinsamen Leitung von Rabin und Ron Rivest. In diesem Verschlüsselungssystem werden die Daten so mit einem öffentlichen Schlüssel verschlüsselt, dass sie nur der Besitzer eines privaten (geheimen) Schlüssels wieder dechiffrieren kann. Derzeit arbeitet Rabin an in der Praxis effizienten zero-knowledge Beweissystemen, mit Anwendungen in Datenschutz und Finanzwirtschaft, etwa bei sicheren Auktionen, Matching-Problemen und zur Überwachung der Regelkonformität.