Michael Rabin (informaticus)

Michael Oser Rabin (Breslau (Duitsland), 1 september 1931) is een Israëlisch informaticus en ontvanger van de Turing Award.

Rabin studeerde af aan de Hebreeuwse Universiteit van Jeruzalem in 1953. Hij behaalde zijn doctorstitel aan de Universiteit van Princeton in 1956.

In 1976 ontving hij samen met Dana Scott de Turing Award:

Voor hun gezamenlijke artikel "Finite Automata and Their Decision Problem," welke het idee van non-deterministische machines introduceert, wat zich heeft bewezen als een enorm waardevol concept. Hun klassieke artikel (Scott & Rabin) vormt een continue bron van inspiratie voor hieropvolgend werk in dit gebied.

Non-deterministische machines zijn een erg belangrijk concept geworden binnen de complexiteitstheorie. Met name met betrekking tot het beschrijven van complexiteitsklassen P en NP.

In 1975 vond Rabin een algoritme voor willekeurige verdeling (Miller-Rabin primality test) uit waarmee men heel snel, weliswaar met een minimale foutmarge, kan bepalen of een bepaald getal een priemgetal is. Deze techniek wordt veelvuldig toegepast binnen de cryptografie. Hij is tevens uitvinder van het Rabin-cryptosysteem.

In 1987 ontwikkelde Rabin, samen met Richard Karp, een van de bekendste efficiënte stringzoekalgoritmen, het stringzoekalgoritme van Rabin-Karp.

Het recente onderzoek van Rabin concentreert zich op computerbeveiliging.

Rabin was van 1983 tot en met 2012 Professor of Computer Science aan de Harvard-universiteit. In 2013 werd hij hier Research Professor of Computer Science.