Michael Rabin

Rabin est né fils de rabbin. Il a obtenu une maîtrise de l'université hébraïque de Jérusalem en 1953 et un doctorat de l'université de Princeton en 1956.

La citation pour le prix Turing, attribué en 1976 conjointement à Michael Rabin et Dana Scott pour un article écrit en 1959, déclare qu'on a accordé la récompense :

« Pour leur article « Finite Automata and Their Decision Problem » présentant l'idée des Automates finis non déterministes qui s'est révélée être un concept d'une énorme valeur. Leur article classique a été une source continue d'inspiration pour le travail qui s'est ensuivi dans ce domaine[1]. »

Les machines non déterministes sont devenues un concept clé dans la théorie de la complexité, en particulier avec la description des classes de complexité P et NP.

En 1957 et 1958, Rabin a démontré que divers problèmes de théorie de groupes sont indécidables (ce sont les premiers du genre après ceux de Sergei Adian en 1955).

En 1969, Rabin a démontré que l'arithmétique monadique du second ordre (avec k successeurs) est décidable[2]. C'est le théorème de Rabin sur les arbres.

En 1974, Rabin a démontré avec Michel Fischer que l'arithmétique de Presburger a une complexité super-exponentielle.

En 1975, Rabin a été un pionnier des algorithmes probabilistes. Il a notamment inventé un algorithme randomisé, le test de primalité de Miller-Rabin, qui détermine très rapidement, mais avec une minuscule probabilité d'erreur, si un nombre est un nombre premier. Cet algorithme est essentiel à l'implémentation de la plupart des algorithmes de cryptographie asymétrique. Il a aussi écrit l'un des premiers algorithmes géométriques probabilistes, pour la recherche des deux points les plus rapprochés[3].

En 1979, Rabin a inventé le cryptosystème de Rabin, qui est le premier cryptosystème asymétrique dont la sécurité se réduit à la difficulté de la factorisation d'un nombre entier.

En 1981, Rabin a inventé la technique du transfert inconscient, permettant à un expéditeur de transmettre un message à un récepteur afin que celui-ci ait une certaine probabilité d'apprendre le message, tandis que l'expéditeur ne sait rien du succès du récepteur.

En 1987, Rabin, ainsi que Richard Karp, a créé un des algorithmes efficaces les plus connus de recherche de chaîne de caractères, l'algorithme de Rabin-Karp.

Les recherches actuelles de Rabin se concentrent sur la sécurité des systèmes informatiques et il est actuellement professeur titulaire de la chaire d'informatique Thomas J. Watson Sr. à l'université Harvard et professeur d'informatique à l'université hébraïque de Jérusalem.

• 1976 : prix Turing
• 2004 : Gödel Lecturer avec une conférence intitulée Proofs persuasions and randomness in mathematics.