Michael Rabin
Michael O. Rabin (Breslau, Duitsland, 1931) is een bekende 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 complexiteitsklasses 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.
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. Momenteel is hij Professor of Computer Science aan de Harvard-universiteit.
